搞懂8大排序算法,這一篇文章就夠了

插入排序

  • 基本思想:每步將一個待排序的紀錄,按其關鍵碼值的大小插入前面已經排序的文件中適當位置上,直到全部插入完為止。
  • 算法適用於少量數據的排序,時間複雜度為O(n^2)。是穩定的排序方法。
  • 代碼:

public static void insertionSort(int[] array){

int tmp;

for(int i=1;i

tmp = array[i]; //將當前位置的數給tmp

int j = i;

for(;j>0&&array[j-1]>tmp;j--){

/* * 往右移,騰出左邊的位置, * array[j-1]>tmp:大於號是升序排列,小於號是降序排列 */

array[j] = array[j-1];

}

//將當前位置的數插入到合適的位置

array[j] = tmp;

}

}

冒泡排序

  • 基本思想:持續比較相鄰的元素。如果第一個比第二個大,就交換他們兩個。直到沒有任何一對數字需要比較。
  • 冒泡排序最好的時間複雜度為O(n)。冒泡排序的最壞時間複雜度為O(n2)。因此冒泡排序總的平均時間複雜度為O(n2)。
  • 算法適用於少量數據的排序,是穩定的排序方法。
  • 代碼:

public static void bubbleSort(int[] array){

int tmp;

boolean flag = false; //設置是否發生交換的標誌

for(int i = array.length-1;i >= 0;i--){

for(int j=0;j

if(array[j]>array[j+1]){

tmp = array[j];

array[j] = array[j+1];

array[j+1] = tmp;

flag = true; //發生了交換

}

}

if(!flag) break; //這一輪循環沒有發生交換,說明排序已經完成,退出循環

}

}

選擇排序

  • 基本思想:每一次從待排序的數據元素中選出最小(或最大)的一個元素,存放在序列的起始位置,直到全部待排序的數據元素排完。
  • 選擇排序是不穩定的排序方法。時間複雜度 O(n^2)。
  • 代碼:

public static void selectSort(int[] array){

for(int i = 0;i

int min = array[i];

int minindex = i;

for(int j = i;j

if(array[j]

min = array[j];

minindex = j;

}

}

if(i != minindex){ //若i不是當前元素最小的,則和找到的那個元素交換

array[minindex] = array[i];

array[i] = min;

}

}

}

希爾排序

  • 基本思想:先取一個小於n的整數d1作為第一個增量,把文件的全部記錄分組。所有距離為d1的倍數的記錄放在同一個組中。先在各組內進行直接插入排序;然後,取第二個增量d2
  • 在使用增量dk的一趟排序之後,對於每一個i,我們都有a[i]<=a[i+dk],即所有相隔dk的元素都被排序。
  • 希爾排序不穩定,時間複雜度 平均時間 O(nlogn) 最差時間O(n^2)
  • 代碼:

public static void shellSort(int[] array){

int j;

for(int gap = array.length/2; gap>0; gap /= 2){

//定義一個增長序列,即分割數組的增量,d1=N/2 dk=(d(k-1))/2

for(int i = gap; i

int tmp = array[i];

for( j =i; j>=gap&&tmp

//將相距為Dk的元素進行排序

array[j] = array[j-gap];

}

array[j] = tmp;

}

}

}

堆排序

  • 預備知識:
  • 二叉堆是完全二元樹(二叉樹)或者是近似完全二元樹(二叉樹)。 二叉堆有兩種:最大堆和最小堆。 大根堆:父結點的鍵值總是大於或等於任何一個子節點的鍵值; 小根堆:父結點的鍵值總是小於或等於任何一個子節點的鍵值。 二叉堆一般用數組來表示。例如,根節點在數組中的位置是0,第n個位置的子節點分別在2n+1和 2n+2。因此,第0個位置的子節點在1和2,1的子節點在3和4。以此類推。這種存儲方式便於尋找父節點和子節點。 例如初始要排序的數組為:49, 38, 65, 97, 76, 13, 27, 49 構造成大根堆之後的數組為:97 76 65 49 49 13 27 38 實際樹形結構如圖(最大堆):
搞懂8大排序算法,這一篇文章就夠了

  • 堆排序基本思想:在排序過程中,將R[l..n]看成是一棵完全二叉樹的順序存儲結構,利用完全二叉樹中雙親結點和孩子結點之間的內在關係【參見二叉樹的順序存儲結構】,在當前無序區中選擇關鍵字最大(或最小)的記錄。堆排序利用了大根堆(或小根堆)堆頂記錄的關鍵字最大(或最小)這一特徵,使得在當前無序區中選取最大(或最小)關鍵字的記錄變得簡單。
  • 堆排序是一種選擇排序,其時間複雜度為O(nlogn)。堆排序是不穩定的
  • 代碼:

/* * 堆排序 * 調整最大堆,交換根元素和最後一個元素。 * 參數說明: * a -- 待排序的數組 */

public static void heapSort(int[] a) {

int n = a.length;

int i,tmp;

// 從(n/2-1) --> 0逐次遍歷。遍歷之後,得到的數組實際上是一個(最大)二叉堆。

for (i = n / 2 - 1; i >= 0; i--)

maxHeapDown(a, i, n-1);

// 從最後一個元素開始對序列進行調整,不斷的縮小調整的範圍直到第一個元素

for (i = n - 1; i > 0; i--) {

// 交換a[0]和a[i]。交換後,a[i]是a[0...i]中最大的。

tmp = a[0];

a[0] = a[i];

a[i] = tmp;

// 調整a[0...i-1],使得a[0...i-1]仍然是一個最大堆。

// 即,保證a[i-1]是a[0...i-1]中的最大值。

maxHeapDown(a, 0, i-1);

}

}

/* * 注:數組實現的堆中,第N個節點的左孩子的索引值是(2N+1),右孩子的索引是(2N+2)。 * 其中,N為數組下標索引值,如數組中第1個數對應的N為0。 * * 參數說明: * a -- 待排序的數組 * start -- 被下調節點的起始位置(一般為0,表示從第1個開始) * end -- 截至範圍(一般為數組中最後一個元素的索引) */

public static void maxHeapDown(int[] a, int start, int end) {

int c = start; // 當前(current)節點的位置

int l = 2*c + 1; // 左(left)孩子的位置

int tmp = a[c]; // 當前(current)節點的大小

for (; l <= end; c=l,l=2*l+1) {

// "l"是左孩子,"l+1"是右孩子

if ( l < end && a[l] < a[l+1])

l++; // 左右兩孩子中選擇較大者,即m_heap[l+1]

if (tmp >= a[l])

break; // 調整結束

else { // 交換值

a[c] = a[l];

a[l]= tmp;

}

}

}

歸併排序

  • 歸併排序的原理:
  • 將待排序的數組分成前後兩個部分,再遞歸的將前半部分數據和後半部分的數據各自歸併排序,得到的兩部分數據,然後使用merge合併算法(算法見代碼)將兩部分算法合併到一起。 例如:如果N=1;那麼只有一個數據要排序,N=2,只需要調用merge函數將前後合併,N=4,........... 也就是將一個很多數據的數組分成前後兩部分,然後不斷遞歸歸併排序,再合併,最後返回有序的數組。
  • 歸併排序的時間複雜度:
  • 歸併排序的最好、最壞和平均時間複雜度都是O(nlogn),而空間複雜度是O(n),比較次數介於(nlogn)/2和(nlogn)-n+1,賦值操作的次數是(2nlogn)。因此可以看出,歸併排序算法比較佔用內存,但卻是效率高且穩定的排序算法。
  • 代碼:

public class MergeSort {

private static void mergeSort(int[] array,int[] tmp,int left,int right){

if(left

int center = ( left + right ) / 2;//取數組的中點

mergeSort(array,tmp,left,center);//歸併排序數組的前半部分

mergeSort(array,tmp,center+1,right);//歸併排序數組的後半部分

merge(array,tmp,left,center+1,right);//將數組的前後半部分合並

}

}

/* * 超簡單的合併函數 */

private static void merge(int[] array, int[] tmp, int leftPos, int rightPos, int rightEnd) {

// TODO Auto-generated method stub

int leftEnd = rightPos - 1;

int tmpPos = leftPos;

int numElements = rightEnd - leftPos + 1;

while(leftPos <= leftEnd && rightPos <= rightEnd){

if(array[leftPos]<=array[rightPos]){

tmp[tmpPos++] = array[leftPos++];

}else{

tmp[tmpPos++] = array[rightPos++];

}

}

while(leftPos <= leftEnd){

tmp[tmpPos++] = array[leftPos++];

}

while(rightPos <= rightEnd){

tmp[tmpPos++] = array[rightPos++];

}

for(int i=0;i

array[rightEnd] = tmp[rightEnd];

}

}

public static void mergeSort(int[] array){

int[] tmp = new int[array.length];//聲明一個用來合併的數組

mergeSort(array,tmp,0,array.length-1);//調用排序函數,傳入數字的起點和終點

}

}

快速排序

  • 快速排序原理:
  1. 如果數組S中元素是0或者1,則返回;
  2. 區數組S中任一元素v,稱之為樞紐元;
  3. 將S-{v}(S中剩餘的元素)劃分成連個不相交的集合:S1={S-{v}|x<=v}和S2={S-{v}|x>=v};
  4. 返回{quicksort(s1)}後跟v,繼而返回{quicksort(S2)}。
  • 選取樞紐元(三數中值分割法)
  • 一般的做法是使用左端、右端和中心位置上的三個元素的中值作為基元。 分割策略: 在分割階段吧所有小元素移到數組的左邊,大元素移到數組右邊。,大小是相對於樞紐元素而言的。 當i在j的左邊時,將i右移,移過哪些小於樞紐元的元素,並將j左移,已過那些大於樞紐元的元素,當i和j停止時,i指向一個大元素,而j指向一個小元素,如果i在j的左邊,那麼將這兩個元素交換,其效果是把一個大元素推向右邊,而把小元素推向左邊。
  • 速排序平均時間複雜度為O(nlogn),最壞情況為O(n^2),n越大,速度越快。不是穩定的排序算法。
  • 代碼:

/* * 快速排序 * 兩個方向,左邊的i下標一直往右走,當a[i] <= a[center_index], * 其中center_index是中樞元素的數組下標,而右邊的j下標一直往左走,當a[j] > a[center_index] * 如果i和j都走不動了,i <= j, 交換a[i]和a[j],重複上面的過程,直到i>j * 交換a[j]和a[center_index],完成一趟快速排序 * 樞軸採用三數中值分割法可以優化 */

//遞歸快速排序

public static void quickSort(int a[]){

qSort(a, 0, a.length - 1);

}

//遞歸排序,利用兩路劃分

public static void qSort(int a[],int low,int high){

int pivot = 0;

if(low < high){

//將數組一分為二

pivot = partition(a,low,high);

//對第一部分進行遞歸排序

qSort(a,low,pivot);

//對第二部分進行遞歸排序

qSort(a,pivot + 1,high);

}

}

//partition函數,實現三數中值分割法

public static int partition(int a[],int low,int high){

int pivotkey = a[low]; //選取第一個元素為樞軸記錄

while(low < high){

//將比樞軸記錄小的交換到低端

while(low < high && a[high] >= pivotkey){

high--;

}

//採用替換而不是交換的方式操作

a[low] = a[high];

//將比樞軸記錄大的交換到高端

while(low < high && a[low] <= pivotkey){

low++;

}

a[high] = a[low];

}

//樞紐所在位置賦值

a[low] = pivotkey;

//返回樞紐所在的位置

return low;

}

桶式排序

  • 桶式排序不再是一種基於比較的排序方法,它是一種比較巧妙的排序方式,但這種排序方式需要待排序的序列滿足以下兩個特徵: 待排序列所有的值處於一個可枚舉的範圍之類; 待排序列所在的這個可枚舉的範圍不應該太大,否則排序開銷太大。
  • 排序的具體步驟如下:
  • (1)對於這個可枚舉範圍構建一個buckets數組,用於記錄“落入”每個桶中元素的個數;
  • (2)將(1)中得到的buckets數組重新進行計算,按如下公式重新計算:
  • buckets[i] = buckets[i] +buckets[i-1] (其中1<=i
  • 桶式排序是一種非常優秀的排序算法,時間效率極高,它只要通過2輪遍歷:第1輪遍歷待排數據,統計每個待排數據“落入”各桶中的個數,第2輪遍歷buckets用於重新計算buckets中元素的值,2輪遍歷後就可以得到每個待排數據在有序序列中的位置,然後將各個數據項依次放入指定位置即可。
  • 桶式排序的空間開銷較大,它需要兩個數組,第1個buckets數組用於記錄“落入”各桶中元素的個數,進而保存各元素在有序序列中的位置,第2個數組用於緩存待排數據.
  • 桶式排序是穩定的。如果待排序數據的範圍在0~k之間,那麼它的時間複雜度是O(k+n)的.
  • 但是它的限制多,比如它只能排整形數組。而且當k較大,而數組長度n較小,即k>>n時,輔助數組C[k+1]的空間消耗較大。當數組為整形,且k和n接近時, 可以用此方法排序。
  • 代碼實現:

//min的值為0,max的值為待排序數組中最大值+1

public static void bucketSort(int[] data, int min, int max) {

// 緩存數組

int[] tmp = new int[data.length];

// buckets用於記錄待排序元素的信息

// buckets數組定義了max-min個桶

int[] buckets = new int[max - min];

// 計算每個元素在序列出現的次數

for (int i = 0; i < data.length; i++) {

buckets[data[i] - min]++;

}

// 計算“落入”各桶內的元素在有序序列中的位置

for (int i = 1; i < max - min; i++) {

buckets[i] = buckets[i] + buckets[i - 1];

}

// 將data中的元素完全複製到tmp數組中

System.arraycopy(data, 0, tmp, 0, data.length);

// 根據buckets數組中的信息將待排序列的各元素放入相應位置

for (int k = data.length - 1; k >= 0; k--) {

data[--buckets[tmp[k] - min]] = tmp[k];

}

}

總結

  • 下面是一個總的表格,大致總結了我們常見的所有的排序算法的特點。
搞懂8大排序算法,這一篇文章就夠了

  • 性能測試
搞懂8大排序算法,這一篇文章就夠了


分享到:


相關文章: