当前位置：首页 > news >正文

★ 数据结构 ★ 排序

news 来源：原创 2025/7/14 12:10:19

Ciallo～(∠・ω< )⌒☆ ~ 今天，我将和大家一起学习数据结构中的各种排序~

❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️

澄岚主页：椎名澄嵐-CSDN博客

数据结构专栏：https://blog.csdn.net/2302_80328146/category_12764674.html?spm=1001.2014.3001.5482

❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️

零测试排序的性能

壹冒泡排序

贰插入排序

叁堆排序

肆希尔排序

伍选择排序

陆快速排序

6.1 hoare版本

6.2 挖坑法

6.3 前后指针法

6.4 非递归快排

柒归并排序

7.1 递归版本

7.2 非递归版本

捌计数排序

玖总结

~ 完 ~

零测试排序的性能

// 测试排序的性能对比
void TestOP()
{srand(time(0));const int N = 100000;int* a1 = (int*)malloc(sizeof(int) * N);int* a2 = (int*)malloc(sizeof(int) * N);int* a3 = (int*)malloc(sizeof(int) * N);int* a4 = (int*)malloc(sizeof(int) * N);int* a5 = (int*)malloc(sizeof(int) * N);int* a6 = (int*)malloc(sizeof(int) * N);for (int i = 0; i < N; ++i){a1[i] = rand();a2[i] = a1[i];a3[i] = a1[i];a4[i] = a1[i];		a5[i] = a1[i];a6[i] = a1[i];}int begin1 = clock();InsertSort(a1, N);int end1 = clock();int begin2 = clock();ShellSort(a2, N);int end2 = clock();int begin3 = clock();SelectSort(a3, N);int end3 = clock();int begin4 = clock();HeapSort(a4, N);int end4 = clock();int begin5 = clock();QuickSort(a5, 0, N - 1);int end5 = clock();int begin6 = clock();MergeSort(a6, N);int end6 = clock();printf("InsertSort:%d\n", end1 - begin1);printf("ShellSort:%d\n", end2 - begin2);printf("SelectSort:%d\n", end3 - begin3);printf("HeapSort:%d\n", end4 - begin4);printf("QuickSort:%d\n", end5 - begin5);printf("MergeSort:%d\n", end6 - begin6);free(a1);free(a2);free(a3);free(a4);free(a5);free(a6);
}

壹冒泡排序

冒泡排序是一种非常容易理解的排序
时间复杂度：O(N ^ 2)
空间复杂度：O(1)
稳定性：稳定

// O(N^2) 最坏
// O(N)   最好
void BubbleSort(int* a, int n)
{for (int j = 0; j < n; j++){// 单趟int flag = 0;for (int i = 0; i < n - j; i++){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);flag = 1;}}if (flag == 0)break;}
}

贰插入排序

插入排序就是把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。

元素集合越接近有序，直接插入排序算法的时间效率越高
时间复杂度：O(N ^ 2)
空间复杂度：O(1)
稳定性：稳定

// 时间复杂度：O(N^2)  什么情况最坏：逆序
// 最好：顺序有序，O(N)
// 插入排序
void Insertsort(int* a, int n)
{// 最后一次 a[n-1] 进到 [0, n - 2] 区间中// end为 n-2for (int i = 0; i < n - 1; i++){// 单趟int end = i;int tmp = a[end + 1];// [0, end]有序 把end+1位置的值插入while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];--end;}else{break;}}// end最后一次会移到-1，不进循环，不能在else中交换a[end + 1] = tmp;}
}

叁堆排序

堆排序即利用堆的思想来进行排序，总共分为两个步骤：

建堆升序：建大堆降序：建小堆
利用堆删除思想来进行排序

void HeapSort(int* a, int n)
{// 向下调整建堆 O(N)for (int i = (n-2)/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;}
}void AdjustDown(int* a, int n, int parent)
{// 先假设左孩子小int child = parent * 2 + 1;while (child < n)  // child >= n说明孩子不存在，调整到叶子了{// 找出小的那个孩子if (child + 1 < n && a[child + 1] > a[child]){++child;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

肆希尔排序

希尔排序的基本思想：先选定一个整数，把待排序文件中所有记录分成gap组，所有距离为gap的记录分在同一组内，并对每一组内的记录进行排序。

希尔排序的特点：

希尔排序是对直接插入排序的优化。
当gap > 1时都是预排序，目的是让数组更接近于有序。
当gap == 1时插入排序，数组已经接近有序的了，这样就会很快。
希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定,大约为O(N ^ 1.3)

void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){gap = gap / 3 + 1; // 保证最后一次gap是1// 有gap组for (int j = 0; j < gap; j++){// 每组排序// 若 i >= n - gap 则最后一次tmp会越界for (size_t i = 0; i < n - gap; i += gap){// 单趟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;}}}
}

// 写法2：多组并行
void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){gap = gap / 3 + 1; // 保证最后一次gap是1for (size_t 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;}}
}

伍选择排序

每一次从待排序的数据元素中选出最小和最大的个元素，存放在序列的起始位置和末位置，直到全部待排序的数据元素排完。

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

好理解，但效率不好。很少使用。
时间复杂度：O(N ^ 2)
空间复杂度：O(1)
稳定性：不稳定

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[maxi]){maxi = i;}if (a[i] < a[mini]){mini = i;}}Swap(&a[mini], &a[begin]);if (begin == maxi){maxi = mini;}Swap(&a[maxi], &a[end]);begin++;end--;}
}

陆快速排序

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

快速排序的特性总结：

1. 快速排序整体的综合性能和使用场景都是比较好的。
2. 时间复杂度：O(N*logN)。

6.1 hoare版本

void QuickSort(int* a, int left, int right)
{if (left >= right)return;// 小区间优化if ((right - left + 1) < 10){InsertSort(a + left, right - left + 1);}int keyi = QuickSortHoare(a, left, right);QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);
}int QuickSortHoare(int* a, int left, int right)
{// 三数取中int midi = GetMid(a, left, right);Swap(&a[left], &a[midi]);int keyi = left;int begin = left, end = right;while (begin < end){while (begin < end && a[end] >= a[keyi]){--end;}while (begin < end && a[begin] <= a[keyi]){++begin;}Swap(&a[begin], &a[end]);}Swap(&a[keyi], &a[begin]);return begin;
}

int GetMid(int* a, int left, int right)
{int midi = (left + right) / 2;if (a[left] < a[midi]){if (a[midi] < a[right]){return midi;}// midi最大else if (a[left] < a[right]){return right;}else{return left;}}else // a[left] > a[midi]{if (a[midi] > a[right]){return midi;}// midi最小else if (a[left] < a[right]){return left;}else{return right;}}
}

6.2 挖坑法

6.3 前后指针法

int QuickSortPointer(int* a, int left, int right)
{// 三数取中int midi = GetMid(a, left, right);Swap(&a[left], &a[midi]);int keyi = left;int prev = left;int cur = prev + 1;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur)Swap(&a[prev], &a[cur]);++cur;}Swap(&a[prev], &a[keyi]);return prev;
}

6.4 非递归快排

int QuickSortNonR(int* a, int left, int right)
{ST st;STInit(&st);STPush(&st, right);STPush(&st, left);while (!STEmpty(&st)){int begin = STTop(&st);STPop(&st);int end = STTop(&st);STPop(&st);int keyi = QuickSortPointer(a, begin, end);// [begin, keyi - 1] keyi [keyi + 1, end]if (keyi + 1 < end){STPush(&st, end);STPush(&st, keyi + 1);}if (begin < keyi - 1){STPush(&st, keyi - 1);STPush(&st, begin);}}STDestory(&st);
}

柒归并排序

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

归并排序的特性总结：

归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
时间复杂度：O(N*logN)
空间复杂度：O(N)
稳定性：稳定

7.1 递归版本

void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail!");return;}_MergeSort(a, tmp, 0, n - 1);free(tmp);tmp = NULL;
}void _MergeSort(int* a, int* tmp, int begin, int end)
{if (begin >= end)return;int mid = (begin + end) / 2;// [begin, mid] [mid + 1, end]有序就可以归并了_MergeSort(a, tmp, begin, mid);_MergeSort(a, tmp, 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, (end - begin + 1) * sizeof(int));
}

7.2 非递归版本

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){for (int i = 0; i < n; i += 2 * gap){// 归并int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;printf("[%d, %d][%d, %d]  ", begin1, end1, begin2, end2);// 第二组都越界，不用归并if (begin2 >= n)break;// begin2没越界，end2越界，修正end2if (end2 >= n)end2 = n - 1;int j = i;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));}gap *= 2;printf("\n");}free(tmp);tmp = NULL;
}

捌计数排序

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

统计相同元素出现次数
根据统计的结果将序列回收到原来的序列中

计数排序的特性：

计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
时间复杂度：O(N + range)
空间复杂度：O(range)

// 时间复杂度：O(N + range)
// 空间复杂度：O(range)
// 整数，范围集中
void CountSort(int* a, int n)
{// 选出max和minint 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){perror("calloc fail!");return;}// 统计次数for (int i = 0; i < n; i++){count[a[i] - min]++;}// 排序int j = 0;for (int i = 0; i < range; i++){while (count[i]--){a[j++] = i + min;}}
}

玖总结

排序种类	时间复杂度	空间复杂度	稳定性
直接插入排序	O(N ^ 2)	O(1)	稳定
希尔排序	O(N ^ 1.3)	O(1)	不稳定
选择排序	O(N ^ 2)	O(1)	不稳定
堆排序	O(N * logN)	O(1)	不稳定
冒泡排序	O(N ^ 2)	O(1)	稳定
快速排序	O(N * logN)	O(logN)	不稳定
归并排序	O(N * logN)	O(N)	稳定

零 测试排序的性能

壹 冒泡排序

贰 插入排序

叁 堆排序

肆 希尔排序

伍 选择排序

陆 快速排序

6.1 hoare版本

6.2 挖坑法

6.3 前后指针法

6.4 非递归快排

柒 归并排序

7.1 递归版本

7.2 非递归版本

捌 计数排序

玖 总结

~ 完 ~

相关文章：

零测试排序的性能

壹冒泡排序

贰插入排序

叁堆排序

肆希尔排序

伍选择排序

陆快速排序

柒归并排序

捌计数排序

玖总结