数据结构（初阶）（八）----排序

排序 概念

排序：所谓排序，就是使⼀串记录，按照其中的某个或某些关键字的⼤⼩，递增或递减的排列起来的 操作。

比较排序 插入排序 直接插入排序

直接插⼊排序是⼀种简单的插⼊排序法，其基本思想是：把待排序的记录按其关键码值的⼤⼩逐个插⼊到⼀个已经排好序的有序序列中，直到所有的记录插⼊完为⽌，得到⼀个新的有序序列 。

希尔排序

希尔排序法⼜称缩⼩增量法。希尔排序法的基本思想是：先选定⼀个整数（通常是gap = n/3+1），把待排序⽂件所有记录分成各组，所有的距离相等的记录分在同⼀组内，并对每⼀组内的记录进⾏排序，然后gap=gap/3+1得到下⼀个整数，再将数组分成各组，进⾏插⼊排序，当gap=1时，就相当于直接插⼊排序。

它是在直接插⼊排序算法的基础上进⾏改进⽽来的，综合来说它的效率肯定是要⾼于直接插⼊排序算法的。

1，gap > 1,预排序

2，gap = 1,直接插入排序（时间复杂度接近O（n））

希尔排序的时间复杂度估算：

外层循环：

外层循环的时间复杂度可以直接给出为： O(log2 n) 或者 O(log3 n) ，即 O(log n)

内层循环：

选择排序

选择排序的基本思想：

每⼀次从待排序的数据元素中选出最⼩（或最⼤）的⼀个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。

直接选择排序

直接选择排序的特性总结：

1，直接选择排序思考⾮常好理解，但是效率不是很好。实际中很少使⽤

2， 时间复杂度： O(N2 )

3，空间复杂度： O(1)

堆排序 交换排序 冒泡排序 快速排序

快速排序是Hoare于1962年提出的⼀种⼆叉树结构的交换排序⽅法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两⼦序列，左⼦序列中所有元素均⼩于基准值，右⼦序列中所有元素均⼤于基准值，然后最左右⼦序列重复该过程，直到所有元素都排列在相应位置上为⽌。

//快速排序 void QuickSort(int* arr, int left, int right) { if (left >= right) return; //确定基准值 int keyi = _QuickSort(arr, left, right); QuickSort(arr, left, keyi-1); QuickSort(arr, keyi+1,right); }

如何将基准值放到相应的位置？

最差情况是n^2

快速排序特性总结：

1，时间复杂度： O(nlogn)

2，空间复杂度： O(logn)

1， hoare版本

算法思路 ：

1，创建左右指针，确定基准值

2，从右向左找出⽐基准值⼩的数据，从左向右找出⽐基准值⼤的数据，左右指针数据交换，进⼊下次循环

//确定基准值 int _QuickSort(int* arr, int left, int right) { int keyi = left; ++left; while (left <= right) { //右边找小 while (left <= right && arr[right] > arr[keyi]) { --right; } //左边找大 while (left <= right && arr[left] < arr[keyi]) { ++left; } if (left <= right) { swap(&arr[left++], &arr[right--]); } } swap(&arr[keyi], &arr[right]); return right; } 2，挖坑法

创建左右指针。⾸先从右向左找出⽐基准⼩的数据，找到后⽴即放⼊左边坑中，当前位置变为新

的"坑"，然后从左向右找出⽐基准⼤的数据，找到后⽴即放⼊右边坑中，当前位置变为新的"坑"，结束循环后将最开始存储的分界值放⼊当前的"坑"中，返回当前"坑"下标（即分界值下标）

//挖坑法 int _QuickSort2(int* arr, int left, int right) { int key = arr[left]; int hole = left; while (left < right) { //右边找小 while (left < right && arr[right] >= key) { --right; } arr[hole] = arr[right]; hole = right; //左边找大 while (left < right && arr[left] <= key) { ++left; } arr[hole] = arr[left]; hole = left; } arr[hole] = key; return hole; } 3，双指针法（lomuto前后指针 ）

//双指针法（lomuto前后指针 ） int _QuickSort3(int* arr, int left, int right) { int key = left; int prev = left; int cur = left + 1; while (cur <= right) { if (arr[cur] < arr[key] && ++prev != cur) { swap(&arr[prev], &arr[cur]); } cur++; } swap(&arr[key], &arr[prev]); return prev; } 非递归版本的快速排序 归并排序

排序算法思想：

归并排序（MERGE-SORT）是建⽴在归并操作上的⼀种有效的排序算法,该算法是采⽤分治法（Divide

and Conquer）的⼀个⾮常典型的应⽤。将已有序的⼦序列合并，得到完全有序的序列；即先使每个

⼦序列有序，再使⼦序列段间有序。若将两个有序表合并成⼀个有序表，称为⼆路归并。

void _MergeSort(int* arr, int left, int right, int* tmp) { if (left >= right) { return; } int mid = (left + right) / 2; _MergeSort(arr, left, mid, tmp); _MergeSort(arr, mid + 1, right, tmp); int begin1 = left, end1 = mid; int begin2 = mid + 1, end2 = right; int index = begin1; while (begin1 <= end1 && begin2 <= end2) { if (arr[begin1] < arr[begin2]) { tmp[index++] = arr[begin1++]; } else { tmp[index++] = arr[begin2++]; } } while (begin1 <= end1) { tmp[index++] = arr[begin1++]; } while (begin2 <= end2) { tmp[index++] = arr[begin2++]; } //拷贝,可以使用memcopy，也可以使用循环 for (int i = left; i <= right; i++) { arr[i] = tmp[i]; } } //归并排序 void MergeSort(int* arr, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc fail"); exit(1); } _MergeSort(arr, 0, n - 1, tmp); free(tmp); tmp = NULL; } 非比较排序 计数排序

计数排序⼜称为鸽巢原理，是对哈希直接定址法的变形应⽤。 操作步骤：

1，统计相同元素出现次数

2，根据统计的结果将序列回收到原来的序列中

//非比较排序 //计数排序 void CountSort(int* arr, int n) { int min = arr[0], max = arr[0]; for (int i = 1; i < n; i++) { if (arr[i] < min) { min = arr[i]; } if (arr[i] > max) { max = arr[i]; } } int range = max - min + 1; int* count = (int*)malloc(sizeof(int)*range); if (count == NULL) { perror("malloc fail"); exit(1); } memset(count, 0, sizeof(int) * range); for (int i = 0; i < n; i++) { count[arr[i] - min]++; } int j = 0; for (int i = 0; i < range; i++) { while (count[i]--) { arr[j++] = i + min; } } } 稳定性

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的

相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，⽽在排序后的序列中，r[i]仍在r[j]之

前，则称这种排序算法是稳定的；否则称为不稳定的。