数据结构之八大排序算法

前言：各位铁子们好啊，博客已经好久没有更新了。今天就来看看新的文章吧。

在日常生活中，我们能够发现在许多地方会存在排序的问题。比如学校排名，成绩排名，手机销量排名等等。而常见的排序有八种，我们一起来看看都有哪八种排序算法。

1. 直接插入排序

直接插入排序的基本思想是：将待排序的关键码值按照大小插入到一个已经有序的序列中，直到将所有的关键码值插入完为止，得到一个新的有序序列。

//时间复杂度O(N^2)void InsertSort(int* arr, int n){for (int i = 0; i < n; ++i){int tmp = arr[i];int end = i - 1;while (end >= 0){if (arr[end] > tmp){arr[end + 1] = arr[end];--end;}else{break;}}arr[end + 1] = tmp;}}

若end>=0，说明应该继续比较当前end所处位置的关键码值与待排序关键码值的大小关系。若end位置的关键码值大，就将end位置的关键码值往后移一步，继续--end，重复上述步骤，直到end位置的关键码值小于等于待排序的关键码值，跳出循环。此时end+1的位置就是待排序关键码值应该插入的位置。

2. 希尔排序

希尔排序是对于直接插入排序的一种优化，又叫做缩小增量法。希尔排序的基本思想是：先选定一个整数（通常是gap=gap/3+1）,把待排序文件所有记录分成各组，所有距离相等的记录分在同一组内，并对每一组内的记录进行排序，然后gap=gap/3+1得到下一个整数，再将数组分成各组，进行插入排序。当gap=1时，就相当于直接插入排序。

void ShellSort(int* arr, int n){int gap = n;//gap > 1都是预排序，目的是为了让数组更接近有序while(gap > 1){//组数越多，循环次数多//组数越少，每组内比较的次数增多//3是一个折中的取法//+1（只有一组，相当于直接插入排序）是为了保证最后一组数据是有序的gap = gap / 3 + 1;for (int j = 0; j < n; ++j){int tmp = arr[j];int end = j - gap;while (end >= 0){if (arr[end] > tmp){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = tmp;}}}

对待排序文件记录进行分组，对每一组的记录先进行排序，若arr[end]>tmp，将当前end位置的记录往后移，更新end，继续判断end位置的关键码值与tmp的大小关系，若arr[end]<tmp，就跳出循环，此时end+gap就是待排序关键码值要插入的位置，再重新分组，重复上述步骤。

希尔排序特性总结：

1.希尔排序是对直接插入排序的优化。

2.gap>1都是预排序，目的是为了让数组更加接近有序，gap=1，就相当于直接插入排序。

3. 直接选择排序

1.在元素集合arr[i]...arr[n-1]选择最小（或最大）的元素2.若它不是这组元素中的第一个（或最后一个）元素时，就将它与这组元素中的第一个（或最后一个）元素进行交换。3.在剩余的元素集合中arr[i+1]...arr[n-2]，重复上述步骤，直到集合剩余一个元素

//时间复杂度O(N^2)//直接选择排序void SelectSort(int* arr, int n){int begin = 0, end = n - 1;while (begin < end){//最小值和最大值都要从begin位置开始找起，因为begin位置的元素有可能就是最大值或最小值int mini = begin, maxi = begin;//找最大，小值for (int i = begin + 1; i <= end; ++i){if (arr[i] > arr[maxi]){maxi = i;}if (arr[i] < arr[mini]){mini = i;}}if (maxi == begin){maxi = mini;}swap(&arr[begin], &arr[mini]);swap(&arr[maxi], &arr[end]);++begin;--end;}}

从begin~end区间内mini找最小值，maxi找最大值，找到后mini位置的元素与begin位置的元素进行交换，maxi与end元素进行交换。

4. 堆排序

堆排序是一种利用堆这种数据结构的排序算法。升序建大堆，降序建小堆。

void AdjustDown(int* arr, int parent, int n){//左孩子int child = 2 * parent + 1;while (child < n){//右孩子大，++childif (child + 1 < n && arr[child + 1] > arr[child]){++child;}//孩子节点大于父节点if (arr[child] > arr[parent]){swap(&arr[child], &arr[parent]);parent = child;child = 2 * parent + 1;}else{break;}}}//堆排序void HeapSort(int* arr, int n){for (int i = (n - 1 - 1) / 2; i >= 0; --i){AdjustDown(arr, i, n);}int end = n - 1;while (end > 0){swap(&arr[0], &arr[end]);AdjustDown(arr, 0, end);--end;}

从最后一棵子树开始进行向下调整算法，直到根节点调整完毕，此时为一个有效的堆。再将根节点与最后一个节点进行交换，调整堆，删除最后一个节点。重复上述步骤，直至元素有序。

5. 归并排序

归并排序采用的是分治法，是将已有序的子序列进行合并，得到一个完全有序的序列。

void _MergeSort(int* arr, int left, int right, int* tmp){if (left >= right){return;}int mid = ((right - left) >> 1) + left;//划分左右区间//左区间 [left,mid]//右区间 [mid + 1,right]_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[begin2++];}else{tmp[index++] = arr[begin1++];}}//若某子数组有剩余元素，则将该数组剩余元素依次填充while (begin1 <= end1){tmp[index++] = arr[begin1++];}while (begin2 <= end2){tmp[index++] = arr[begin2++];}for (int i = left; i <= right; ++i){arr[i] = tmp[i];}}//归并排序void MergeSort(int* arr, int n){int* tmp = (int*)malloc(sizeof(int) * n);_MergeSort(arr, 0, n - 1, tmp);free(tmp);}

对一个序列不断地进行划分左右区间，直到不能划分为止，再对子区间依次进行排序，合并即可。

6. 计数排序（非比较排序）

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

1.统计相同元素出现次数。

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

//计数排序void CountSort(int* arr, int n){//求数组内最大，最小值int max = arr[0], min = arr[0];for (int i = 0; i < n; ++i){if (arr[i] > max){max = arr[i];}if (arr[i] < min){min = arr[i];}}//开空间int gap = max - min + 1;int* count = (int*)calloc(sizeof(int), gap);//统计每一个元素出现的次数for (int i = 0; i < n; ++i){count[arr[i] - min]++;}//排序int index = 0;for (int i = 0; i < gap; ++i){while (count[i]--){arr[index++] = i + min;}}free(count);}

之所以开空间没有按照元素的个数去开空间，是因为如果元素个数非常庞大的情况下，可能会申请失败，浪费空间。因此对原数组进行遍历，求数组内的最大值和最小值，再开辟空间。统计原数组内每一个元素出现的次数，根据统计的结果对序列进行排序

7. 快速排序

快速排序的基本思想：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后对左右子序列重复该过程。

7.1 hoare版本的快速排序

思路：

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

2.从右往左找比基准值小的，从左往右找比基准值大的，左右指针数据交换，进行下次循环。

//hoare版本int _QuickSort(int* arr, int left, int right){int key = left;//如果不++left，那么当right指向的数据都大于key(基准//值)时，会存在越界问题++left;while (left <= right){//从右往左找比基准值小的while (left <= right && arr[right] > arr[key])//arr[right] == arr[key]要不要交换{--right;}//从左往右找比基准值大的while (left <= right && arr[left] < arr[key]){++left;}if (left <= right){swap(&arr[left++], &arr[right--]);}}swap(&arr[right], &arr[key]);return right;}

right指针从右往左找比基准值小的数据，left指针从左往右找比基准值大的数据，左右指针数据进行交换，继续重复上述步骤。跳出循环之后，right指向的位置就是基准值的位置。

7.2 挖坑法

思路：

创建左右指针。首先从右往左找比基准值小的数据，找到后放入左边坑中，当前位置变为新的“坑”；然后从左往右找比基准值大的数据，找到后放入右边坑中，当前位置变为新的“坑”，结束循环后，将基准值放入当前“坑”中，返回当前“坑”下标。

//挖坑法int _QuickSort1(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;}

7.3 lomuto前后指针法

思路：
创建前后指针，从左往右找比基准值小的数据进行交换，使小的数据都排在基准值左边。

int _QuickSort2(int* arr, int left, int right){int key = left;int prev = left, cur = prev + 1;while (cur <= right){//从左往右找比基准值小的数据if (arr[cur] < arr[key] && ++prev != cur){swap(&arr[prev], &arr[cur]);}++cur;}swap(&arr[prev], &arr[key]);return prev;}//快速排序void QuickSort(int* arr, int left, int right){if (left >= right){return;}int key = _QuickSort(arr, left, right);//划分左右序列QuickSort(arr, left, key - 1);QuickSort(arr, key + 1, right);}

基准值确定之后，在对原数组进行左右区间划分，重复上述步骤。

7.4 非递归版本的快速排序

//非递归版本（栈实现）void QuickSortNonR(int* arr, int left, int right){Stack s;//栈初始化StackInit(&s);//栈顶插入数据StackPush(&s, right);StackPush(&s, left);//判断栈是否为空while (!StackEmpty(&s)){//取栈顶数据int begin1 = StackTop(&s);StackPop(&s);int end1 = StackTop(&s);StackPop(&s);int key = begin1;int prev = begin1;int cur = prev + 1;while (cur <= end1){if (arr[cur] < arr[key] && ++prev != cur){swap(&arr[cur], &arr[prev]);}++cur;}swap(&arr[prev], &arr[key]);if (prev + 1 < end1){StackPush(&s,end1);StackPush(&s, prev + 1);}if (begin1 < prev - 1){StackPush(&s, prev - 1);StackPush(&s, begin1);}}StackDestroy(&s);}

先入右区间的左右端点，再入左区间的左右端点，因为栈遵从先入后出的原则。