一、排序的概述
排序：所謂排序，就是使一串記錄，按照其中的某個或某些關(guān)鍵字的大小，遞增或遞減的排列起來的操作。
八大排序都屬于內(nèi)部排序，也就是只考慮數(shù)據(jù)量較小僅需要使用內(nèi)存的排序算法，他們之間關(guān)系如下：
什么是排序的穩(wěn)定性?
穩(wěn)定性：假定在待排序的記錄序列中，存在多個具有相同的關(guān)鍵字的記錄，若經(jīng)過排序，這些記錄的相對次序保持
不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩(wěn)
定的；否則稱為不穩(wěn)定的。
該排序即為不穩(wěn)定的排序，因為相同的4在排序之后順序變了。
二、插入排序
當(dāng)插入第i(i>=1)個元素時，前面的array[0],array[1],…,array[i-1]已經(jīng)排好序，此時用array[i]的排序碼與array[i-1],array[i-2],…的排序碼順序進行比較，找到插入位置即將array[i]插入，原來位置上的元素順序后移
說的通俗一點就是每次默認(rèn)前面的元素是有序的，然后用該位置的元素就尋找合適位置插入。
那插入排序的時間復(fù)雜度是多少嗎?
因為每一位都需要和前面有序數(shù)組的每一位去比較所以時間復(fù)雜度為O(n).
最好情況下，當(dāng)數(shù)組有序時，每個數(shù)字只需要比較一次，最優(yōu)時間復(fù)雜度為O(1).
/**
* 插入排序
* 時間復(fù)雜度 : O(n2)
* 最好情況下 有序 時間復(fù)雜度 O(n)
* 空間復(fù)雜度: O(1)
* 穩(wěn)定性: 穩(wěn)定
* 一個本身就穩(wěn)定的排序可以實現(xiàn)為不穩(wěn)定的排序
* 一個本身就不穩(wěn)定的排序能變成穩(wěn)定的排序嗎？
* @param arr
*/
public static void insertSort(int[] arr) {
//插入排序
for (int i = 1; i < arr.length; i++) {
int j = i - 1;
int tmp = arr[i];
while(j >= 0) {
if(arr[j] > tmp) {
arr[j+1] = arr[j];
} else {
break;
}
j--;
}
arr[j+1] = tmp;
}
}
三、希爾排序
希爾排序按其設(shè)計者希爾（Donald Shell）的名字命名，該算法由希爾在 1959 年所發(fā)表的論文“A high-speed sorting procedure” 中所描述。
希爾排序法又稱縮小增量法。希爾排序法的基本思想是：先選定一個整數(shù)，把待排序文件中所有記錄分成個組，所有距離為的記錄分在同一組內(nèi)，并對每一組內(nèi)的記錄進行排序。然后，取，重復(fù)上述分組和排序的工作。當(dāng)?shù)竭_=1時，所有記錄在統(tǒng)一組內(nèi)排好序。
希爾排序主要是對插入排序進行了優(yōu)化，因為當(dāng)數(shù)組為逆序時，插入排序會變得十分的慢，希爾排序在最后一次插入排序之前進行了預(yù)排序。
希爾排序的特性總結(jié)：
- 希爾排序是對直接插入排序的優(yōu)化。
- 當(dāng)gap > 1時都是預(yù)排序，目的是讓數(shù)組更接近于有序。當(dāng)gap == 1時，數(shù)組已經(jīng)接近有序的了，這樣就會很快。這樣整體而言，可以達到優(yōu)化的效果。我們實現(xiàn)后可以進行性能測試的對比。
- 希爾排序的時間復(fù)雜度不好計算，因為gap的取值方法很多，導(dǎo)致很難去計算，因此在好些樹中給出的希爾排序的時間復(fù)雜度都不固定：
/**
* 希爾排序
* O(n^1.3次方)
* @param
*/
public static void shellSort(int[] arr) {
//希爾排序
int gap = arr.length;
while(gap > 1) {
gap /= 2;
shell(arr,gap);
}
}
public static void shell(int[] arr,int gap) {
for (int i = gap; i < arr.length; i++) {
int tmp = arr[i];
int j = i - gap;
for (; j >= 0; j-=gap) {
if(arr[j] > tmp) {
arr[j + gap] = arr[j];
}else {
break;
}
}
arr[j + gap] = tmp;
}
}
四、 選擇排序
每一次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€元素，存放在序列的起始位置，直到全部待排序的數(shù)據(jù)元素排完
選擇排序的思想特別簡單，就是每一趟確定一個最大值或者最小值，數(shù)組遍歷完成后數(shù)組也就有序了。
1.在元素集合array[i]–array[n-1]中選擇關(guān)鍵碼最大(小)的數(shù)據(jù)元素
2.若它不是這組元素中的最后一個(第一個)元素，則將它與這組元素中的最后一個（第一個）元素交換
3.在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重復(fù)上述步驟，直到集合剩余1個元素
/**
* 選擇排序
* 時間復(fù)雜度: O(n2)
* 與數(shù)組是否有序無關(guān)
* 空間復(fù)雜度: O(1)
* 穩(wěn)定性: 不穩(wěn)定
* @param
*/
public static void selectSort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if(arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if(minIndex != i) {
int h = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = h;
}
}
}
選擇排序?qū)崿F(xiàn)起來比較簡單，但時間復(fù)雜度相對比較高達到了O(n)，我們能不能對此進行優(yōu)化一下。
我們遍歷一趟數(shù)組，找到一個最大值的下標(biāo)和最小值的下標(biāo)，一趟下來就直接確定了最大值和最小值，這樣就能優(yōu)化一點。
public static void selectSort2(int[] arr){
int left = 0;
int right = arr.length - 1;
while(left < right) {
int minIndex = left;
int maxIndex = left;
for (int i = left + 1; i <= right; i++) {
if(arr[i] < arr[minIndex]) {
minIndex = i;
}
if(arr[i] > arr[maxIndex]) {
maxIndex = i;
}
}
swap(arr,left,minIndex);
//如果maxIndex == left證明已經(jīng)把最大值放到了minIndex位置
if(maxIndex == left) {
maxIndex = minIndex;
}
swap(arr,right,maxIndex);
left++;
right--;
}
}
public static void swap(int[] arr,int l,int r) {
int tmp = arr[l];
arr[l] = arr[r];
arr[r] = tmp;
}
我們發(fā)現(xiàn)當(dāng)數(shù)組首位置的元素就是最大值時，我們可以發(fā)現(xiàn)在進行最小值交換后，最大值的數(shù)被換到了minIndex位置，所以我們要進行那樣的判斷。
五、 堆排序
堆排序(Heapsort)是指利用堆積樹（堆）這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法，它是選擇排序的一種。它是通過堆
來進行選擇數(shù)據(jù)。需要注意的是排升序要建大堆，排降序建小堆。
大概的流程就是如果需要排一個升序數(shù)組，那么就建一個大根堆，然后每次將堆頂元素和最后一個位置的元素交換，然后在將堆頂元素進行向下操作。這樣我們就能每次選擇一個數(shù)組最大值放到尾部。
/**
* 堆排序
* 時間復(fù)雜度 : O(n * logn)
* 空間復(fù)雜度: O(1)
* @param
*/
public static void heapSort(int[] arr) {
createBigHeap(arr);
int end = arr.length - 1;
while(end > 0) {
swap(arr,0,end);
shiftDown(arr,0,end);
end--;
}
}
public static void createBigHeap(int[] arr) {
for (int i = (arr.length - 1 - 1) / 2; i >= 0; i--) {
shiftDown(arr,i,arr.length);
}
}
public static void shiftDown(int[] arr,int parent,int len) {
int child = parent * 2 + 1;
while (child < len) {
if(child + 1 < len && arr[child + 1] > arr[child]) {
child++;
}
if(arr[child] > arr[parent]) {
swap(arr,child,parent);
} else {
break;
}
parent = child;
child = parent * 2 + 1;
}
}
public static void swap(int[] arr,int l,int r) {
int tmp = arr[l];
arr[l] = arr[r];
arr[r] = tmp;
}
1. 堆排序使用堆來選數(shù)，效率就高了很多。
2. 時間復(fù)雜度：O(N*logN)
3. 空間復(fù)雜度：O(1)
4. 穩(wěn)定性：不穩(wěn)定
六、 冒泡排序
基本思想：所謂交換，就是根據(jù)序列中兩個記錄鍵值的比較結(jié)果來對換這兩個記錄在序列中的位置，交換排序的特
點是：將鍵值較大的記錄向序列的尾部移動，鍵值較小的記錄向序列的前部移動。
我們可以發(fā)現(xiàn)每進行一次排序就能確定一個最大值出來，N個數(shù)需要進行N-1趟冒泡。
/**
* 冒泡排序
* 時間復(fù)雜度 O(n2)
* 空間復(fù)雜度 O(1)
* 穩(wěn)定的排序
* @param
*/
public static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
boolean flg = false;
for (int j = 0; j < arr.length - i - 1; j++) {
if(arr[j] > arr[j + 1]) {
flg = true;
swap(arr,j,j+1);
}
}
if(flg == false) {
break;
}
}
}
public static void swap(int[] arr,int l,int r) {
int tmp = arr[l];
arr[l] = arr[r];
arr[r] = tmp;
}
1. 冒泡排序是一種非常容易理解的排序
2. 時間復(fù)雜度：O(N^2)
3. 空間復(fù)雜度：O(1)
4. 穩(wěn)定性：穩(wěn)定
七、 快速排序
快速排序是Hoare于1962年提出的一種二叉樹結(jié)構(gòu)的交換排序方法，其基本思想為：任取待排序元素序列中的某元素作為基準(zhǔn)值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準(zhǔn)值，右子序列中所有元素均大于基準(zhǔn)值，然后最左右子序列重復(fù)該過程，直到所有元素都排列在相應(yīng)位置上為止。
上述為快速排序遞歸實現(xiàn)的主框架，發(fā)現(xiàn)與二叉樹前序遍歷規(guī)則非常像，同學(xué)們在寫遞歸框架時可想想二叉樹前序遍歷規(guī)則即可快速寫出來，后序只需分析如何按照基準(zhǔn)值來對區(qū)間中數(shù)據(jù)進行劃分的方式即可。
public static void quickSort(int[] arr) {
quick(arr,0,arr.length - 1);
}
public static void quick(int[] arr,int start,int end) {
if(start >= end) {
return;
}
int pivot = partition2(arr,start,end);
quick(arr,start,pivot - 1);
quick(arr,pivot + 1,end);
}
我們每次主要要去寫找基準(zhǔn)的方法，這里我們一共有三種找基準(zhǔn)的方法。
將區(qū)間按照基準(zhǔn)值劃分為左右兩半部分的常見方式有：
Hoare版
public static int partition(int[] arr,int left,int right) {
//Hoare法
int i = left;
int pivot = arr[left];
while(left < right) {
while(left < right && arr[right] >= pivot) {
right--;
}
while (left < right && arr[left] <= pivot) {
left++;
}
swap(arr,left,right);
}
swap(arr,i,left);
return left;
}
挖坑法
public static int partition1(int[] arr,int left,int right) {
//挖坑法
int i = left;
int j = right;
int pivot = arr[left];
while(i < j) {
while(i < j && arr[j] >= pivot) {
j--;
}
arr[i] = arr[j];
while (i < j && arr[i] <= pivot) {
i++;
}
arr[j] = arr[i];
}
arr[i] = pivot;
return i;
}
前后指針
public static int partition2(int[] arr,int left,int right) {
//前后指針法
int prev = left;
int cur = left + 1;
int pivot = arr[left];
while(cur <= right) {
if(arr[cur] < pivot && arr[++prev] != arr[cur]) {
swap(arr,prev,cur);
}
cur++;
}
swap(arr,left,prev);
return prev;
}
快速排序問題解答
為什么要先移動右邊？
答案：為了保證當(dāng)left和right相遇時，left指向的元素是小于pivot的。大家可以手動的畫圖理解一下。
為什么要包含等號?
為了避免這個情況的出現(xiàn)，排序陷入死循環(huán)。
時間復(fù)雜度分析
這是快速排序的理想狀態(tài)下，那當(dāng)不理想呢?
當(dāng)數(shù)組有序時,時間復(fù)雜度達到了O(n2)，空間復(fù)雜度達到了O(n),那如何優(yōu)化呢？
快速排序的優(yōu)化
三數(shù)取中法
每次基準(zhǔn)值，在數(shù)組首元素，中間值，和末尾值取一個中位數(shù)。
這些就可以避免數(shù)組有序時造成O(n2)的情況
public static void quick(int[] arr,int start,int end) {
if(start >= end) {
return;
}
//在進行partition盡量去解決不均勻問題
int mid = findMidValueOfIndex(arr,start,end);
swap(arr,mid,start);
int pivot = partition2(arr,start,end);
quick(arr,start,pivot - 1);
quick(arr,pivot + 1,end);
}
public static int findMidValueOfIndex(int[] arr,int start,int end) {
int mid = (end + start) / 2;
if(arr[start] < arr[end]) {
if(arr[mid] < arr[start]) {
return start;
}else if(arr[mid] > arr[end]) {
return end;
}else {
return mid;
}
}else {
if(arr[mid] < arr[end]) {
return end;
}else if(arr[mid] > arr[start]) {
return start;
}else {
return mid;
}`在這里插入代碼片`
}
}
嵌套插入排序
當(dāng)快速排序在最后幾層時，數(shù)組已經(jīng)趨于有序，在進行快速排序進行遞歸次數(shù)過多，這是我們可以進行插入排序。
public static void quick(int[] arr,int start,int end) {
if(start >= end) {
return;
}
//當(dāng)數(shù)組快趨于有序時，進行插入排序
if((end - start + 1) <= 15) {
insert(arr,start,end);
}
//在進行partition盡量去解決不均勻問題
int mid = findMidValueOfIndex(arr,start,end);
swap(arr,mid,start);
int pivot = partition2(arr,start,end);
quick(arr,start,pivot - 1);
quick(arr,pivot + 1,end);
}
public static void insert(int[] arr,int left,int right) {
for (int i = left + 1; i <= right; i++) {
int j = i + 1;
for (; j >= 0; j--) {
if(arr[j] > arr[i]) {
arr[j + 1] = arr[j];
}else {
break;
}
}
arr[j + 1] = arr[i];
}
}
非遞歸實現(xiàn)
public static void quickSort1(int[] arr) {
Stack<Integer> stack = new Stack<>();
int left = 0;
int right = arr.length - 1;
int pivot = partition(arr,left,right);
//判斷左邊是不是有兩個元素
if(left < pivot - 1) {
stack.push(left);
stack.push(pivot - 1);
}
//判斷右邊是否有兩個元素
if(right > pivot + 1) {
stack.push(pivot + 1);
stack.push(right);
}
while (!stack.isEmpty()) {
right = stack.pop();
left = stack.pop();
pivot = partition(arr,left,right);
//判斷左邊是不是有兩個元素
if(left < pivot - 1) {
stack.push(left);
stack.push(pivot - 1);
}
//判斷右邊是否有兩個元素
if(right > pivot + 1) {
stack.push(pivot + 1);
stack.push(right);
}
}
}
快速排序總結(jié)
- 快速排序整體的綜合性能和使用場景都是比較好的，所以才敢叫快速排序
- 時間復(fù)雜度：O(N*logN)
- 空間復(fù)雜度：O(logN)
- 穩(wěn)定性：不穩(wěn)定
八、 歸并排序
歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。 歸并排序核心步驟：
/**
* 歸并排序
* 時間復(fù)雜度: O(n*logn)
* 空間復(fù)雜度: O(N) //因為創(chuàng)建了臨時數(shù)組
* 穩(wěn)定性: 穩(wěn)定
* @param
*/
public static void mergeSort(int[] arr) {
mergeSortChild(arr,0,arr.length - 1);
}
public static void mergeSortChild(int[] arr,int left,int right) {
if(left >= right) {
return;
}
int mid = (left + right) / 2;
mergeSortChild(arr,left,mid);
mergeSortChild(arr,mid + 1,right);
//合并
merge(arr,left,mid,right);
}
public static void merge(int[] arr,int left,int mid,int right) {
int[] array = new int[right - left + 1];
int l = left;
int l1 = mid;
int r = mid + 1;
int r1 = right;
int k = 0;
while(l <= l1 && r <= r1) {
if(arr[l] < arr[r]) {
array[k++] = arr[l++];
} else {
array[k++] = arr[r++];
}
}
while(l <= l1) {
array[k++] = arr[l++];
}
while(r <= r1){
array[k++] = arr[r++];
}
//保證left到right之間的數(shù)據(jù)是有序的
for (int i = 0; i < array.length; i++) {
arr[left + i] = array[i];
}
}
非遞歸實現(xiàn)
//非遞歸實現(xiàn)歸并排序
public static void mergeSort1(int[] arr) {
int gap = 1;
while(gap < arr.length) {
for (int i = 0; i < arr.length; i+=gap*2) {
int left = i;
int mid = left + gap - 1;
if(mid >= arr.length) {
mid = arr.length - 1;
}
int right = mid + gap;
if(right >= arr.length) {
right = arr.length - 1;
}
merge(arr,left,mid,right);
}
gap *= 2;
}
}
海量數(shù)據(jù)排序
外部排序：排序過程需要在磁盤等外部存儲進行的排序
前提：內(nèi)存只有 1G，需要排序的數(shù)據(jù)有 100G
因為內(nèi)存中因為無法把所有數(shù)據(jù)全部放下，所以需要外部排序，而歸并排序是最常用的外部排序
- 先把文件切分成 200 份，每個 512 M
- 分別對 512 M 排序，因為內(nèi)存已經(jīng)可以放的下，所以任意排序方式都可以
- 進行 2路歸并，同時對 200 份有序文件做歸并過程，最終結(jié)果就有序了
九、 基數(shù)排序(了解)
前面我們介紹的七種排序都是基于比較的排序，現(xiàn)在我們來了解幾種不用比較的排序
空間換取時間，入的次數(shù)和出的次數(shù)取決于數(shù)據(jù)里面的最大值
public class RadixSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
// 對 arr 進行拷貝，不改變參數(shù)內(nèi)容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
int maxDigit = getMaxDigit(arr);
return radixSort(arr, maxDigit);
}
/**
* 獲取最高位數(shù)
*/
private int getMaxDigit(int[] arr) {
int maxValue = getMaxValue(arr);
return getNumLenght(maxValue);
}
private int getMaxValue(int[] arr) {
int maxValue = arr[0];
for (int value : arr) {
if (maxValue < value) {
maxValue = value;
}
}
return maxValue;
}
protected int getNumLenght(long num) {
if (num == 0) {
return 1;
}
int lenght = 0;
for (long temp = num; temp != 0; temp /= 10) {
lenght++;
}
return lenght;
}
private int[] radixSort(int[] arr, int maxDigit) {
int mod = 10;
int dev = 1;
for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
// 考慮負數(shù)的情況，這里擴展一倍隊列數(shù)，其中 [0-9]對應(yīng)負數(shù)，[10-19]對應(yīng)正數(shù) (bucket + 10)
int[][] counter = new int[mod * 2][0];
for (int j = 0; j < arr.length; j++) {
int bucket = ((arr[j] % mod) / dev) + mod;
counter[bucket] = arrayAppend(counter[bucket], arr[j]);
}
int pos = 0;
for (int[] bucket : counter) {
for (int value : bucket) {
arr[pos++] = value;
}
}
}
return arr;
}
/**
* 自動擴容，并保存數(shù)據(jù)
*
* @param arr
* @param value
*/
private int[] arrayAppend(int[] arr, int value) {
arr = Arrays.copyOf(arr, arr.length + 1);
arr[arr.length - 1] = value;
return arr;
}
}
十、 八種排序時間復(fù)雜度比較
比較排序中是穩(wěn)定排序的有: 插入排序，冒泡排序，歸并排序
十一、 計數(shù)排序
思想：計數(shù)排序又稱為鴿巢原理，是對哈希直接定址法的變形應(yīng)用。 操作步驟：
- 統(tǒng)計相同元素出現(xiàn)次數(shù)
- 根據(jù)統(tǒng)計的結(jié)果將序列回收到原來的序列中
/**
* 計數(shù)排序
* 適合數(shù)值范圍小的數(shù)組
* 時間復(fù)雜度為O(n+數(shù)值范圍)
* 空間復(fù)雜度: O(范圍)
* @param arr
*/
public static void countSort(int[] arr) {
int min = arr[0];
int max = arr[0];
//遍歷數(shù)組 找最大值 最小值
for (int i = 0; i < arr.length; i++) {
if(arr[i] < min) {
min = arr[i];
}
if(arr[i] > max) {
max = arr[i];
}
}
//開辟一個計數(shù)數(shù)組，數(shù)組大小為數(shù)組值的取值范圍
int[] ret = new int[max - min + 1];
//統(tǒng)計每個數(shù)字出現(xiàn)的次數(shù)
for (int i = 0; i < arr.length; i++) {
ret[arr[i] - min]++;
}
int k = 0;
for (int i = 0; i < ret.length; i++) {
while(ret[i] > 0) {
arr[k++] = i + min;
ret[i]--;
}
}
}
時間復(fù)雜度:
時間復(fù)雜度為O(n+數(shù)值范圍)
計數(shù)排序適用于數(shù)值范圍較小的數(shù)組
十二、 桶排序
桶排序（Bucket sort）或所謂的箱排序，是一個排序算法，工作的原理是將數(shù)組分到有限數(shù)量的桶里。每個桶再個別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進行排序），最后依次把各個桶中的記錄列出來記得到有序序列。桶排序是鴿巢排序的一種歸納結(jié)果。當(dāng)要被排序的數(shù)組內(nèi)的數(shù)值是均勻分配的時候，桶排序使用線性時間（Θ(n)）。但桶排序并不是比較排序，他不受到O(n log n)下限的影響。文章來源：http://www.zghlxwxcb.cn/news/detail-830786.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-830786.html
public static void bucketsort(int[] arr) {
ArrayList bucket[] = new ArrayList[6];// 聲明六個桶
for (int i = 0; i < bucket.length; i++) {
bucket[i] = new ArrayList<Integer>();// 確定桶的格式為ArrayList
}
for (int i = 0; i < arr.length; i++) {
int index = arr[i] / 10;// 確定元素存放的桶號
bucket[index].add(arr[i]);// 將元素存入對應(yīng)的桶中
}
for (int i = 0; i < bucket.length; i++) {
bucket[i].sort(null);// 對每一個桶排序，默認(rèn)排序方式
for (int i1 = 0; i1 < bucket[i].size(); i1++) {// 遍歷桶中的元素并輸出
System.out.print(bucket[i].get(i1) + " ");
}
}
}
到了這里，關(guān)于十大排序算法(java實現(xiàn)萬字詳解)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
