目錄

一、插入排序

1、直接插入排序

1.1、排序方法

1.2、圖解分析

1.3、代碼實(shí)現(xiàn)

2、希爾排序

2.1、排序方法

2.2、圖解分析

2.3、代碼實(shí)現(xiàn)

二、選擇排序

1、直接選擇排序

1.1、排序方法

1.2、圖解分析

1.3、代碼實(shí)現(xiàn)

2、堆排序

2.1、排序方法

2.2、圖解分析

2.3、代碼實(shí)現(xiàn)

三、交換排序

1、冒泡排序

1.1、排序方法

1.2、圖解分析

1.3、代碼實(shí)現(xiàn)

2、快速排序

2.1、hoare排序

2.1.1、圖解分析

2.1.2、代碼實(shí)現(xiàn)

2.2、挖坑法

2.2.1、圖解分析

2.2.2、代碼實(shí)現(xiàn)

2.3、前后指針法

2.3.1、圖解分析

2.3.2、代碼實(shí)現(xiàn)

四、歸并排序

1、排序方法

2、圖解分析

3、代碼實(shí)現(xiàn)

---

一、插入排序

? ? ? ? 基本思想：把待排序的數(shù)據(jù)按其關(guān)鍵碼值的大小追個(gè)插入到一個(gè)有序序列中，得到一個(gè)新的有序序列。

1、直接插入排序

1.1、排序方法

? ? ? ? 當(dāng)插入第i個(gè)元素時(shí)，數(shù)組的前i-1個(gè)元素已經(jīng)有序，將第i個(gè)元素與前i-1個(gè)元素的關(guān)鍵碼值進(jìn)行比較，找到合適的位置插入，并將該位置之后的所有元素順序后移即可。

1.2、圖解分析

1.3、代碼實(shí)現(xiàn)

// 直接插入排序
void InsertSort(int* a, int n)
{for (int i = 0; i < n; i++){int tmp = a[i];int end = i-1;while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];end--;}else{break;}}a[end + 1] = tmp;;}
}

2、希爾排序

2.1、排序方法

? ? ? ? 希爾排序是對直接插入排序的優(yōu)化。希爾排序的基本思想是：先選定一個(gè)合理的增量gap，把待排序文件中的數(shù)據(jù)分成gap個(gè)組，每一組中的相鄰元素位置相差gap的距離，對每組元素各自進(jìn)行直接插入排序。然后適當(dāng)縮小gap，重復(fù)上述操作。直到gap等于1時(shí)，所有元素在同一組內(nèi)最后一次直接插入排序。

2.2、圖解分析

2.3、代碼實(shí)現(xiàn)

// 希爾排序
void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){bool change = false;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;change = true; }else{break;}}a[end + gap] = tmp;;}if (change == false){break;}}
}

二、選擇排序

? ? ? ? 基本思想：每次從待排序元素中選出最大（或最小）的一個(gè)元素將其存放在已有序序列的后一個(gè)位置，重復(fù)操作直到所有元素存放結(jié)束得到一個(gè)有序的新序列。

1、直接選擇排序

1.1、排序方法

? ? ? ? 在元素集合arr[i]~arr[n-1]中選出關(guān)鍵碼值最大（小）的元素，若該元素不是第一個(gè)（或最后一個(gè)），則將其與這組元素中的第一個(gè)（或最后一個(gè)）元素進(jìn)行交換，對剩余未排序元素重復(fù)上述操作直到結(jié)束。

1.2、圖解分析

1.3、代碼實(shí)現(xiàn)

// 選擇排序
void SelectSort(int* a, int n)
{int begin_i = 0;int end_i = n-1;while (begin_i < end_i){int max_i = end_i;int min_i = begin_i;for (int i = begin_i; i <= end_i; i++){if (a[i] < a[min_i]){Swap(&a[i], &a[min_i]);}if (a[i] > a[max_i]){Swap(&a[i], &a[max_i]);}}begin_i++;end_i--;}
}

2、堆排序

2.1、排序方法

? ? ? ? 堆排序的操作對象是堆，排序會調(diào)整部分節(jié)點(diǎn)在堆中的相對位置，為了不破壞堆的性質(zhì)，我們將堆頂節(jié)點(diǎn)與堆的最后一個(gè)節(jié)點(diǎn)交換，再將除最后一個(gè)節(jié)點(diǎn)之外的其他節(jié)點(diǎn)通過向下調(diào)整算法調(diào)整成為一個(gè)新的堆。重復(fù)操作直到只剩下一個(gè)節(jié)點(diǎn)為止。

2.2、圖解分析

2.3、代碼實(shí)現(xiàn)

//堆排序typedef struct Heap
{int* a;int size;int capacity;
}Heap;//向下調(diào)整算法
void AdjustDwon(int* a, int n, Heap* hp)
{for (int parent = (n - 2) / 2; parent >= 0; parent--){int child = parent * 2 + 1;while (child < n){bool change = false;if (child + 1 < n){child = hp->a[child] > hp->a[child + 1] ? child : child + 1;}if (hp->a[child] > hp->a[parent]){int tmp = hp->a[parent];hp->a[parent] = hp->a[child];hp->a[child] = tmp;change = true;parent = child;child = parent * 2 + 1;}if (change == false){break;}}}
}//初始化堆
void InitialHeap(Heap* hp,int n)
{if (!hp){return;}int* tmp = (int*)malloc(sizeof(int) * n);if (!tmp){perror("InitialHeap::malloc:");return;}hp->a = tmp;hp->size = 0;hp->capacity = n;
}//創(chuàng)建堆
void HeapBuild(Heap* hp, int* a, int n)
{assert(hp);for (int i = 0; i < n; i++){hp->a[i] = a[i];}AdjustDwon(a, n, hp);
}//排序
void Sort(Heap* hp, int* a, int n)
{int end = n - 1;while (end > 0){int tmp = hp->a[0];hp->a[0] = hp->a[end];hp->a[end] = tmp;a[end] = hp->a[end];end--;AdjustDwon(a, end, hp);}a[0] = hp->a[0];
}

三、交換排序

? ? ? ? 基本思想：根據(jù)序列中兩個(gè)元素的關(guān)鍵碼值的大小來判斷是否需要交換他們在序列中的位置，默認(rèn)將關(guān)鍵碼值較大的元素向序列的尾部移動，關(guān)鍵碼值較小的元素向序列的首部移動。

1、冒泡排序

1.1、排序方法

? ? ? ? 冒泡排序是將待排序元素的關(guān)鍵碼值最大（小）的元素通過從前往后依次兩兩比較交換到最后面的位置。每操作一次可以確定一個(gè)元素在有序序列中的的位置。

1.2、圖解分析

1.3、代碼實(shí)現(xiàn)

// 冒泡排序
void BubbleSort(int* a, int n)
{for (int j = 1; j < n; j++){for (int i = 0; i < n - j; i++){if (a[i] > a[i + 1]){int tmp = a[i];a[i] = a[i + 1];a[i + 1] = tmp;}}}
}

2、快速排序

? ? ? ? 基本思想：快速排序是任取待排序元素序列中的某元素的關(guān)鍵碼值作為基準(zhǔn)值，按照該基準(zhǔn)值將待排序集合分割成左右兩個(gè)子序列，左子序列中所有元素均小于基準(zhǔn)值，右子序列中所有元素均大于基準(zhǔn)值，再對左右子序列重復(fù)該過程直到結(jié)束。

2.1、hoare排序

2.1.1、圖解分析

????????key選左邊，從右邊出發(fā)。保證了相遇位置的值比key位置的值小；

????????key選右邊，從左邊出發(fā)。保證了相遇位置的值比key位置的值大；

? ? ? ? （注意：key指的是下標(biāo)）

2.1.2、代碼實(shí)現(xiàn)

// 快速排序hoare版本
int PartSort1(int* a, int left, int right)
{int key = left;while (left < right){while (left < right && a[right] >= a[key]){right--;}while (left<right && a[left]<=a[key]){left++;}int tmp = a[right];a[right] = a[left];a[left] = tmp;}int tmp = a[key];a[key] = a[left];a[left] = tmp;return left;
}

2.2、挖坑法

2.2.1、圖解分析

? ? ?（?注意： 這里的key是一個(gè)變量，不是下標(biāo)）

2.2.2、代碼實(shí)現(xiàn)

// 快速排序挖坑法
int PartSort2(int* a, int left, int right)
{int key = a[left];int hole = left;while (left < right){while (hole < right){if (a[right] < key){a[hole] = a[right];hole = right;break;}right--;}while (hole > left){if (a[left] > key){a[hole] = a[left];hole = left;break;}left++;}}a[hole] = key;return hole;
}

2.3、前后指針法

2.3.1、圖解分析

????????（這里的key同樣是一個(gè)變量，不是下標(biāo)）

2.3.2、代碼實(shí)現(xiàn)

// 快速排序前后指針法
int PartSort3(int* a, int left, int right)
{int prev = left;int cur = prev + 1;int key = a[left];while (cur <= right){if (a[cur] < key){prev++;int tmp = a[prev];a[prev] = a[cur];a[cur] = tmp;}cur++;}a[left] = a[prev];a[prev] = key;return prev;
}

四、歸并排序

1、排序方法

????????歸并排序是建立在歸并操作上的一種排序算法。歸并排序是將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)字序列有序，再使子序列段間有序。歸并排序的核心思想是先分解后合并。

2、圖解分析

3、代碼實(shí)現(xiàn)

// 歸并排序遞歸實(shí)現(xiàn)void _MergeSort(int* a, int begin, int end, int* tmp)
{if (begin >= end){return;}int mid = (begin + end) / 2;_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid + 1, end, tmp);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("MergeSort-->malloc:");return;}_MergeSort(a, 0, n - 1, tmp);free(tmp);tmp = NULL;
}