数据结构：直接插入排序，希尔排序，选择排序，堆排序，冒泡排序，快速排序，归并排序，计数排序(C实现)
个人主页 ： 个人主页
个人专栏 ： 《数据结构》 《C语言》
文章目录
- 前言
- 一、插入排序
- 1.直接插入排序
- 2.希尔排序
- 二、选择排序
- 1. 选择排序
- 2.堆排序
- 三、交换排序
- 1.冒泡排序
- 2.快速排序(递归)
- a.hoare版(PartSort1)
- b.挖坑法(PartSort2)
- c.前后指针法(PartSort3)
- 3.快速排序(非递归)
- 四、归并排序
- 归并排序(递归)
- 归并排序(非递归)
- 五、计数排序
- 总结
前言
排序：使一串数据，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
一、插入排序
插入排序的思路：把待排序数组，逐个插入到已经排好序的有序数组中，直到所有待排序数组插入完成，的到一个新的有序数组。
1.直接插入排序
假如要排序为升序数组。
遍历待排序数组，将待排序数组元素与已排序数组元素比较，如果已排序数组元素大于待排序数组元素，已排序数组元素后移，待排序数组再次于前一个已排序数组比较，直到遍历完已排序数组或待排序数组元素大于已排序数组元素。
// 插入排序 //遍历待排序数组，每次选择数组元素 与 已排序数组元素比较，如果该数组元素小于已排序数组元素，已排序元素后移 //直到该数组元素遍历到首或大于已排序数组元素，插入该位置。 void InsertSort(int* a, int n) { for (int i = 0; i = 0) { if (tmp- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：稳定
2.希尔排序
我们要知道 待排序数组越接近有序，直接插入排序算法的时间效率越高。
那么我们如果使一个待排序数组快速变成接近有序的数组，再对接近有序的数组进行一次直接插入排序，就是希尔排序。
- 那对于希尔排序的一个问题，如何使待排序数组快速变成接近有序数组？
这就要使用gap(增益变量)，对待排序数组每隔gap的元素进行直接插入排序，再对待排序数组每隔(gap/2)的元素进行直接插入排序，再对待排序数组每隔(gap/2)的元素进行直接插入排序…
直到gap为1时，待排序数组已经接近有序数组。在对待排序数组直接插入排序即可。
如下：对数组{9,1,2,5,7,4,8,6,3,5}进行希尔排序
// 希尔排序 //1、使待排序数组变成接近有序的数组 2、对接近有序的数组直接插入排序 O(n) //使用gap(增益变量)来使待排序数组快速变成接近有序的数组 void ShellSort(int* a, int n) { int gap = n; while (gap > 1) { gap = gap / 3 + 1; // + 1 保证最后一次排序一定是插入排序 or gap /= 2 for (int i = 0; i = 0) { if (a[j] > tmp) { a[j + gap] = a[j]; } else { break; } j -= gap; } a[j + gap] = tmp; } } }- 时间复杂度：O(N^1.3)
- 空间复杂度：O(1)
- 稳定性：不稳定
二、选择排序
选择排序的思想：每次从待排序数组中选择出最大or最小的元素，放入已排序数组后，直到待排序数组中没有元素时，数组完成排序。
1. 选择排序
每次从待排序数组中选择最小的元素，与已排序数组的后一个元素交换，直到待排序数组中没有元素结束。
// 选择排序 //遍历待排序数组，每次选择最小的待排序数组元素，与待排序数组首元素交换。 void SelectSort(int* a, int n) { for (int i = 0; i a[j]) { minIndex = j; } } swap(&a[minIndex], &a[i]); } }- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：稳定
2.堆排序
堆排序详解
堆排序就是将待排序数组，构建为大堆(升序)or小堆(降序)，然后将堆顶元素与待排序数组最后元素交换，删除堆最后的数据，再次选择新的堆顶元素。重复上述操作即可。
如下： 对数组 {16, 72, 31, 94, 53, 23}降序
// 堆排序 //升序建大堆 void AdjustDwon(int* a, int n, int parent) { int child = parent * 2 + 1; while (parent = 0; i--) { AdjustDwon(a, n, i); } int end = n - 1; while (end > 0) { swap(&a[0], &a[end]); AdjustDwon(a, end, 0); end--; } }- 时间复杂度：O(N*logN)
- 空间复杂度：O(1)
- 稳定性：不稳定
三、交换排序
交换排序思想：根据待排序数组中两个元素的比较结果交换两个元素在待排序数组中的位置。
1.冒泡排序
从待排序数组中每次比较相邻的两个元素，如果前一个元素大于后一个元素，交换两个元素。如果前一个元素小于等于后一个元素，不变。继续向后比较相邻的两个元素。
void swap(int* a, int* b) { int tmp = *a; *a = *b; *b = tmp; } // 冒泡排序 void BubbleSort(int* a, int n) { for (int i = 0; i a[j + 1]) { flag = 0; swap(&a[j], &a[j + 1]); } } //如果flag == 1表示这趟比较，并未交换元素，表示数组已经有序 if (flag == 1) { break; } } }- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：稳定
2.快速排序(递归)
快速排序(递归)思路：任取待排序数组中的某个元素为基准值，以该基准值为标准，将待排序数组分成左右两个子序列，左子序列都小于基准值，右子序列都大于该基准值，然后左右子序列重复该操作，直到左右子序列只有一个元素or没有元素结束，此时数组有序。
//类似于二叉树的先序遍历 void QuickSort(int* a, int left, int right) { if (left >= right) return; int pivot = PartSort3(a, left, right); //int pivot = PartSort2(a, left, right); //int pivot = PartSort1(a, left, right); //区间[left, pivot - 1] pivot [pivot + 1, right] QuickSort(a, left, pivot - 1); QuickSort(a, pivot + 1, right); }那么快排是如何以基准值来区分左右子序列？
a.hoare版(PartSort1)
以待排序数组第一个元素为基准值，定义两个变量(left，right)分别指向待排序数组的左右边界。
先移动right，找到小于基准值的元素，right停止移动。移动left，找到大于基准值的元素，left停止移动，交换left 与 right的元素。重复上述操作，直到left 与 right 指向同一个元素，交换此时基准值 与 left指向的元素。就完成了以基准值为标准，将数组分成左右子数组。
如下：对数组{6,1,2,7,9,3,4,5,10,8}以6为基准值，来划分左右子序列
注意：
如何保证left 与 right 相遇的位置值一定小于基准值？
left 与 right相遇有两种情况：
- left 遇到 right ，此时right已经停止移动，代表right已经找到了小于基准值的元素，left 与 right相遇的值小于基准值
- right 遇到 left，上一次left 与 right 都找到相应元素并交换 or 此时left指向的就是数组最左边，此时left指向元素小于等于基准值，left 与 right相遇的值小于基准值
这是以右边界为基准值为列。如果以左边界为基准值，要保证left 与 right相遇元素小于基准值，要left先移动。
left要不要从基准值的位置开始移动？
- left必须从基准值的位置开始移动，假设对数组{0,2,5,9,1,3}进行快排，如果以0为基准值，left从2的位置开始移动，会导致2到0的左边去，使数组变为{2,0,5,9,1,3}。就不符合快排的划分。
//三数取中 针对已经有序的数组 int GetMiddle(int* a, int left, int right) { int mid = (right - left) / 2 + left; if (a[mid] > a[left]) { if (a[mid] a[right]) { //right a[left]) { //mid a[left]) { //mid a[left]) { //mid = n) end2 = n - 1; int j = begin1; while (begin1 if (a[begin1] tmp[j++] = a[begin1++]; } else { tmp[j++] = a[begin2++]; } } while (begin1 tmp[j++] = a[begin1++]; } while (begin2 tmp[j++] = a[begin2++]; } memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1)); }//for (int i = 0; i
- left必须从基准值的位置开始移动，假设对数组{0,2,5,9,1,3}进行快排，如果以0为基准值，left从2的位置开始移动，会导致2到0的左边去，使数组变为{2,0,5,9,1,3}。就不符合快排的划分。
- 那对于希尔排序的一个问题，如何使待排序数组快速变成接近有序数组？
