本章我們來學(xué)習(xí)一下數(shù)據(jù)結(jié)構(gòu)的排序算法！

目錄

1.排序的概念及其運(yùn)用

1.1排序的概念

1.2?常見的排序算法

2.常見排序算法的實(shí)現(xiàn)

2.1 插入排序

2.1.1基本思想：

2.1.2直接插入排序：

2.1.3 希爾排序( 縮小增量排序 )

2.2 選擇排序

2.2.1基本思想：

2.2.2 直接選擇排序:

2.2.3 堆排序

2.3 交換排序

2.3.1冒泡排序

2.3.2 快速排序

1. hoare版本

2. 挖坑法

3. 前后指針版本??編輯

2.3.2 快速排序優(yōu)化

?2.3.3?快速排序非遞歸

2.4 歸并排序

2.5 非比較排序

3.排序算法復(fù)雜度及穩(wěn)定性分析

1.排序的概念及其運(yùn)用

1.1排序的概念

（1）排序：所謂排序，就是使一串記錄，按照其中的某個(gè)或某些關(guān)鍵字的大小，遞增或遞減的排列起來的操作。

（2）穩(wěn)定性：假定在待排序的記錄序列中，存在多個(gè)具有相同的關(guān)鍵字的記錄，若經(jīng)過排序，這些記錄的相對(duì)次???序保持不變，即在原序列中，??r [ i ] = r?[ j ]，且?r [ i ]?在?r [ j ]?之前，而在排序后的序列中，??r [ i ]?仍在?r [ j ]之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。

（3）內(nèi)部排序：數(shù)據(jù)元素全部放在內(nèi)存中的排序。

（4）外部排序：數(shù)據(jù)元素太多不能同時(shí)放在內(nèi)存中，根據(jù)排序過程的要求不能在內(nèi)外存之間移動(dòng)數(shù)據(jù)的排序。

1.2?常見的排序算法

2.常見排序算法的實(shí)現(xiàn)

2.1 插入排序

2.1.1基本思想：

直接插入排序是一種簡單的插入排序法，其基本思想是：

????????把待排序的記錄按其關(guān)鍵碼值的大小逐個(gè)插入到一個(gè)已經(jīng)排好序的有序序列中，直到所有的記錄插入完為止，得到一個(gè)新的有序序列 。

2.1.2直接插入排序：

// 時(shí)間復(fù)雜度：O(N^2) 逆序
// 最好的情況：O(N)  順序有序
void InsertSort(int* a, int n)
{// [0, end] end+1for (int i = 0; i < n-1; ++i){int end = i;int tmp = a[end + 1];while (end >= 0){if (tmp > a[end]){a[end + 1] = a[end];--end;}else{break;}}a[end + 1] = tmp;}
}

直接插入排序的特性總結(jié)：

????????1. 元素集合越接近有序，直接插入排序算法的時(shí)間效率越高。

????????2. 時(shí)間復(fù)雜度： O(N^2)

????????3. 空間復(fù)雜度： O(1) ，它是一種穩(wěn)定的排序算法。

????????4. 穩(wěn)定性：穩(wěn)定

2.1.3 希爾排序( 縮小增量排序 )

?

?代碼案例：

// 平均O(N^1.3)
void ShellSort(int* a, int n)
{int gap = n;// gap > 1時(shí)是預(yù)排序，目的讓他接近有序// gap == 1是直接插入排序，目的是讓他有序while (gap > 1){//gap = gap / 2;gap = gap / 3 + 1;for (int i = 0; i < n - gap; ++i){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}

希爾排序的特性總結(jié)：

????????1. 希爾排序是對(duì)直接插入排序的優(yōu)化。

????????2. 當(dāng) gap > 1 時(shí)都是預(yù)排序，目的是讓數(shù)組更接近于有序。當(dāng) gap == 1 時(shí)，數(shù)組已經(jīng)接近有序的了，這樣就會(huì)很快。這樣整體而言，可以達(dá)到優(yōu)化的效果。我們實(shí)現(xiàn)后可以進(jìn)行性能測試的對(duì)比。

????????3. 希爾排序的時(shí)間復(fù)雜度不好計(jì)算，因?yàn)?/span> gap 的取值方法很多，導(dǎo)致很難去計(jì)算，因此在好些書中給出的希爾排序的時(shí)間復(fù)雜度都不固定：

《數(shù)據(jù)結(jié)構(gòu) (C 語言版 ) 》 --- 嚴(yán)蔚敏

?《數(shù)據(jù)結(jié)構(gòu)-用面相對(duì)象方法與C++描述》--- 殷人昆

因?yàn)間ap是按照Knuth提出的方式取值的，而且Knuth進(jìn)行了大量的試驗(yàn)統(tǒng)計(jì)，我們暫時(shí)就按照： 到? 來算。

????????4. 穩(wěn)定性：不穩(wěn)定

2.2 選擇排序

2.2.1基本思想：

2.2.2 直接選擇排序:

??代碼案例：

// 時(shí)間復(fù)雜度：O(N^2)
// 最好的情況下：O(N^2)
void SelectSort(int* a, int n)
{int begin = 0, end = n - 1;while (begin < end){int mini = begin, maxi = begin;for (int i = begin + 1; i <= end; ++i){if (a[i] < a[mini]){mini = i;}if (a[i] > a[maxi]){maxi = i;}}Swap(&a[begin], &a[mini]);if (maxi == begin){maxi = mini;}Swap(&a[end], &a[maxi]);++begin;--end;}
}

直接選擇排序的特性總結(jié)：

????????1. 直接選擇排序思考非常好理解，但是效率不是很好。實(shí)際中很少使用。

????????2. 時(shí)間復(fù)雜度： O(N^2)

????????3. 空間復(fù)雜度： O(1)

????????4. 穩(wěn)定性：不穩(wěn)定

2.2.3 堆排序

?

?代碼案例：

void AdjustDown(int* a, int size, int parent)
{int child = parent * 2 + 1;while (child < size){// 假設(shè)左孩子小，如果解設(shè)錯(cuò)了，更新一下if (child + 1 < size && a[child + 1] > a[child]){++child;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}// 升序
void HeapSort(int* a, int n)
{// O(N)// 建大堆for (int i = (n - 1 - 1) / 2; i >= 0; --i){AdjustDown(a, n, i);}// O(N*logN)int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}
}

堆排序的特性總結(jié)：

????????1. 堆排序使用堆來選數(shù)，效率就高了很多。

????????2. 時(shí)間復(fù)雜度： O(N*logN)

????????3. 空間復(fù)雜度： O(1)

????????4. 穩(wěn)定性：不穩(wěn)定

2.3 交換排序

2.3.1冒泡排序

?代碼案例：

void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}// 時(shí)間復(fù)雜度：O(N^2)
// 最好情況是多少：O(N)
void BubbleSort(int* a, int n)
{for (int j = 0; j < n; j++){bool exchange = false;for (int i = 1; i < n-j; i++){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);exchange = true;}}if (exchange == false)break;}

冒泡排序的特性總結(jié)：

????????1. 冒泡排序是一種非常容易理解的排序

????????2. 時(shí)間復(fù)雜度： O(N^2)

????????3. 空間復(fù)雜度： O(1)

????????4. 穩(wěn)定性：穩(wěn)定

2.3.2 快速排序

?代碼案例：

// 假設(shè)按照升序?qū)rray數(shù)組中[left, right)區(qū)間中的元素進(jìn)行排序
void QuickSort(int array[], int left, int right)
{if(right - left <= 1)return;// 按照基準(zhǔn)值對(duì)array數(shù)組的 [left, right)區(qū)間中的元素進(jìn)行劃分int div = partion(array, left, right);// 劃分成功后以div為邊界形成了左右兩部分 [left, div) 和 [div+1, right)// 遞歸排[left, div)QuickSort(array, left, div);// 遞歸排[div+1, right)QuickSort(array, div+1, right);
}int GetMidi(int* a, int begin, int end)
{int midi = (begin + end) / 2;// begin end midi三個(gè)數(shù)選中位數(shù)if (a[begin] < a[midi]){if (a[midi] < a[end])return midi;else if (a[begin] > a[end])return begin;elsereturn end;}else{//...}
}void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;int midi = GetMidi(a, begin, end);Swap(&a[midi], &a[begin]);int left = begin, right = end;int keyi = begin;while (left < right){// 右邊找小while (left < right && a[right] >= a[keyi]){--right;}// 左邊找大while (left < right && a[left] <= a[keyi]){++left;}Swap(&a[left], &a[right]);}Swap(&a[left], &a[keyi]);keyi = left;// [begin, keyi-1] keyi [keyi+1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi+1, end);
}

1. hoare版本

代碼案例：

int PartSort1(int* a, int begin, int end)
{int midi = GetMidi(a, begin, end);Swap(&a[midi], &a[begin]);int left = begin, right = end;int keyi = begin;while (left < right){// 右邊找小while (left < right && a[right] >= a[keyi]){--right;}// 左邊找大while (left < right && a[left] <= a[keyi]){++left;}Swap(&a[left], &a[right]);}Swap(&a[left], &a[keyi]);return left;
}void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;int keyi = PartSort1(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi+1, end);
}

2. 挖坑法

?代碼案例：

// 挖坑法
int PartSort2(int* a, int begin, int end)
{int midi = GetMidi(a, begin, end);Swap(&a[midi], &a[begin]);int key = a[begin];int hole = begin;while (begin < end){// 右邊找小，填到左邊的坑while (begin < end && a[end] >= key){--end;}a[hole] = a[end];hole = end;// 左邊找大，填到右邊的坑while (begin < end && a[begin] <= key){++begin;}a[hole] = a[begin];hole = begin;}a[hole] = key;return hole;
}void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;int keyi = PartSort2(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi+1, end);
}

3. 前后指針版本?

?代碼案例：

int PartSort3(int* a, int begin, int end)
{int midi = GetMidi(a, begin, end);Swap(&a[midi], &a[begin]);int keyi = begin;int prev = begin;int cur = prev + 1;while (cur <= end){if (a[cur] < a[keyi] && ++prev != cur)Swap(&a[prev], &a[cur]);++cur;}Swap(&a[prev], &a[keyi]);keyi = prev;return keyi;
}void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;int keyi = PartSort3(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi+1, end);
}

2.3.2 快速排序優(yōu)化

1. 三數(shù)取中法選 key

2. 遞歸到小的子區(qū)間時(shí)，可以考慮使用插入排序

?2.3.3?快速排序非遞歸

?代碼案例：

void QuickSortNonR(int* a, int left, int right)
{Stack st;StackInit(&st);StackPush(&st, left);StackPush(&st, right);while (StackEmpty(&st) != 0){right = StackTop(&st);StackPop(&st);left = StackTop(&st);StackPop(&st);if(right - left <= 1)continue;int div = PartSort1(a, left, right);// 以基準(zhǔn)值為分割點(diǎn)，形成左右兩部分：[left, div) 和 [div+1, right)StackPush(&st, div+1);StackPush(&st, right);StackPush(&st, left);StackPush(&st, div);}StackDestroy(&s);
}

快速排序的特性總結(jié)：

????????1. 快速排序整體的綜合性能和使用場景都是比較好的，所以才敢叫 快速 排序

????????2. 時(shí)間復(fù)雜度： O(N*logN)

3. 空間復(fù)雜度： O(logN)

4. 穩(wěn)定性：不穩(wěn)定

2.4 歸并排序

基本思想：

????????歸并排序（MERGE-SORT ）是建立在歸并操作上的一種有效的排序算法 , 該算法是采用分治法（ Divide and Conquer）的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為二路歸并。 歸并排序核心步驟：

??代碼案例：

void _MergeSort(int* a, int begin, int end, int* tmp)
{if (begin >= end)return;int mid = (begin + end) / 2;// [begin, mid][mid+1, end]_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid+1, end, tmp);// [begin, mid][mid+1, end]歸并int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int i = begin;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[i++] = a[begin1++];}else{tmp[i++] = a[begin2++];}}while(begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}_MergeSort(a, 0, n - 1, tmp);free(tmp);
}//非遞歸法
void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}int gap = 1;while (gap < n){printf("gap:%2d->", gap);for (size_t i = 0; i < n; i += 2 * gap){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;// [begin1, end1][begin2, end2] 歸并//printf("[%2d,%2d][%2d, %2d] ", begin1, end1, begin2, end2);// 邊界的處理if (end1 >= n || begin2 >= n){break;}if (end2 >= n){end2 = n - 1;}//printf("[%2d,%2d][%2d, %2d] ", begin1, end1, begin2, end2);int j = begin1;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}memcpy(a + i, tmp + i, sizeof(int) * (end2-i+1));}printf("\n");gap *= 2;}free(tmp);
}

歸并排序的特性總結(jié)：

????????1. 歸并的缺點(diǎn)在于需要 O(N) 的空間復(fù)雜度，歸并排序的思考更多的是解決在磁盤中的外排序問題。

????????2. 時(shí)間復(fù)雜度： O(N*logN)

????????3. 空間復(fù)雜度： O(N)

????????4. 穩(wěn)定性：穩(wěn)定

2.5 非比較排序

思想：計(jì)數(shù)排序又稱為鴿巢原理，是對(duì)哈希直接定址法的變形應(yīng)用。 操作步驟：

????????1. 統(tǒng)計(jì)相同元素出現(xiàn)次數(shù)

????????2. 根據(jù)統(tǒng)計(jì)的結(jié)果將序列回收到原來的序列中

?代碼案例：

// 基數(shù)排序/桶排序// 計(jì)數(shù)排序
// 時(shí)間：O(N+range)
// 空間：O(range)
void CountSort(int* a, int n)
{int min = a[0], max = a[0];for (int i = 1; i < n; i++){if (a[i] < min)min = a[i];if (a[i] > max)max = a[i];}int range = max - min + 1;int* count = (int*)calloc(range, sizeof(int));if (count == NULL){printf("calloc fail\n");return;}// 統(tǒng)計(jì)次數(shù)for (int i = 0; i < n; i++){count[a[i] - min]++;}// 排序int i = 0;for (int j = 0; j < range; j++){while (count[j]--){a[i++] = j + min;}}
}

計(jì)數(shù)排序的特性總結(jié)：

????????1. 計(jì)數(shù)排序在數(shù)據(jù)范圍集中時(shí)，效率很高，但是適用范圍及場景有限。

????????2. 時(shí)間復(fù)雜度： O(MAX(N, 范圍 ))

????????3. 空間復(fù)雜度： O( 范圍 )

????????4. 穩(wěn)定性：穩(wěn)定

3.排序算法復(fù)雜度及穩(wěn)定性分析

?

?注：

? ? ? ? （1）算法穩(wěn)定性是指，待排序列中相同的值在排序后相對(duì)順序不變，這就是算法穩(wěn)定。

????????（2）輔助空間是指在排序的過程中開辟了新的空間。

?本篇完！