【数据结构】排序合集_资讯

【数据结构】排序合集

创始人

2025-05-31 15:54:00

0次

排序的概念：排序：使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

一、插入排序

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

直接插入排序

当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移。

void InsertSort(int* a, int n)
{for (int i = 0; i < n - 1; i++)  //总的循环次数为n-1,因为最后一个数组元素为a[end+1]{int end = i;int tmp = a[end + 1];  //保存下一个位置的元素，因为挪动位置会覆盖while (end >= 0){if (a[end] > tmp) //如果要升序排序，最后一个元素比要插入的数据大，就去挪动位置{a[end + 1] = a[end];--end;}else{break;}}a[end + 1] = tmp;  //挪动好位置后就去插入}
}

直接插入排序的特性总结：

1. 元素集合越接近有序，直接插入排序算法的时间效率越高

2. 时间复杂度：O(N^2)

3. 空间复杂度：O(1)，它是一种稳定的排序算法

4. 稳定性：稳定

2. 希尔排序

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。总结希尔排序分两步1.预排序2.直接插入排序

void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){gap = gap / 3 + 1;  //gap为一组进行预排序for (int i=0; i < n - gap; i++){int end = i;int tmp = a[end + gap];while (end >= 0){if (a[end] > tmp) //a[end]比我大，就去挪动位置{a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp; //到了这一行有两种情况：1.end<0说明tmp元素得在头部插入}                       //2.tmp>a[end] ，到了该插入的位置了}
}

希尔排序的特性总结：

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

2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。

3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此可以粗略的认为希尔排序的时间复杂度为O(N^1.3).

二、选择排序

基本思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

直接选择排序

思想：遍历一遍数组，选出最小的数据和最大的数据，小的数据放在最左边，大的数据放最右边。第二次遍历数组，之前排好序的就不再参与遍历和数据交换，以此类推。

void SelectSort(int* a, int n)
{int  begin = 0;int end = n - 1;while (begin < end){int mini = begin;int 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[begin], &a[mini]);  //最小的换到beginif (maxi == begin)  //最大的数据在begin位置被换走后需要更新数组的下标{maxi == mini;}Swap(&a[end], &a[maxi]);++begin;--end;}
}

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

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

2. 时间复杂度：O(N^2)

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

4. 稳定性：不稳定

堆排序

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

void AdjustDown(int* a, int n, int parent)  
{int minChild = parent * 2 + 1;  //默认最小的孩子为左孩子while (minChild < n){if (minChild + 1 < n && a[minChild + 1] > a[minChild])  //更新孩子的下标{minChild++;}if (a[minChild] > a[parent]){Swap(&a[minChild], &a[parent]);parent = minChild;minChild = parent * 2 + 1;}else{break;}}
}void HeapSort(int* a, int n)
{//向下调整建堆for (int i = (n - 2) / 2; i >= 0; i--){AdjustDown(a, n, i);}
//选数：建大堆，最大的数据在最上方，与最后一个位置交换，最大的数就放在了最后一个位置，然后就
//不再参与剩下的调整任务了，可以看作是堆外的数据。让换到a[0]位置的元素向下调整到符合堆性质的位置，此时堆的最上方
//又产生了一个最大的数据，然后与堆的最后一个数据交换位置再向下调整，以此类推。int i = 1;while (i < n){Swap(&a[0], &a[n - i]);AdjustDown(a, n - i, 0);++i;}
}

堆排序总结：

1. 堆排序使用堆来选数，效率就高了很多。

2. 时间复杂度：O(N*logN)

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

4. 稳定性：不稳定

三、交换排序

基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动

冒泡排序

思想：从第一个数据开始往后遍历数组，如果前一个数据元素的值大于后一个数据元素的值，那就交换两个数据的位置，直到数组的最后一个数据，这样一趟排序就可以选出最大的数据并且放到了数组的最后一个位置。接下来的每次选数，上一轮选出来的数据就不参与比较了，因为大的数据都到了数组的后方。

void BubbleSort(int* a, int n)
{for (int j = 0; j < n; ++j){int exchange = 0;for (int i = 0; i < n - 1 - j; ++i){if (a[i] > a[i + 1]){Swap(&a[i], &a[i + 1]);exchange = 1;}}if (exchange == 0)   //如果exchange在这次的循环中没有改变  说明没有需要交换的元素了，已经是有序的状态了 {break;}}
}

冒泡排序的特性总结：

1. 冒泡排序是一种非常容易理解的排序

2. 时间复杂度：O(N^2)

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

4. 稳定性：稳定

快速排序

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

int GetMidIndex(int* a, int left, int right)  //三数取中
{int mid = left+(right-left) / 2;if (a[left] < a[mid]){if (a[mid] < a[right]){return mid;}else if (a[left] > a[right]){return left;}else{return right;}}else // a[left] >= a[mid]{if (a[mid] > a[right]){return mid;}else if (a[left] < a[right]){return left;}else{return right;}}
}//hoare版本  
int PartSort1(int* a, int left, int right)
{//三数取中int mid = GetMidIndex(a, left, right);Swap(&a[left], &a[mid]);  int keyi = left;while (left < right){// R找小while (left < right && a[right] >= a[keyi]){--right;}// L找大while (left < right && a[left] <= a[keyi]){++left;}if (left < right)Swap(&a[left], &a[right]);}int meeti = left;Swap(&a[meeti], &a[keyi]);return meeti;
}//挖坑法 推荐使用
int PartSort2(int* a, int left, int right)
{int mid = GetMidIndex(a, left, right);Swap(&a[left], &a[right]);int key = a[left];int hole = left;while (left < right){//右边找小，填到左坑while(left= key){--right;}a[hole] = a[right];hole = right;//左边找大，填到右边的坑while (left= end)  //只有一个数或者区间不存在{return;}if (end - begin <= 8)  //小优化 ：最后的三层用插入排序，因为最后几层的节点个数很多，要是继续递归代价很大{InsertSort(a + begin, end - begin + 1);}else{int keyi = PartSort2(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);}
}
//快速排序优化：
//1. 三数取中法选key
//2. 递归到小的子区间时，可以考虑使用插入排序

快排总结：

时间复杂度O(N*logN)

空间复杂度：O(logN)

稳定性：不稳定

四、归并排序

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

思想：把长度为n的输入序列分成两个长度为n/2的子序列，对这两个子序列分别采用归并排序；将两个排序好的子序列合并成一个最终的排序序列。

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, (end - begin + 1) * sizeof(int));
}void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");exit(-1);}_MergeSort(a, 0, n - 1, tmp);free(tmp);tmp = NULL;
}

归并排序总结：

1. 时间复杂度：O(N*logN)

2. 空间复杂度：O(N)

3. 稳定性：稳定

五、计数排序

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。计数排序不是基于比较的排序算法。而是作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 Θ(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。该算法时间复杂度为O(n+k)。

void CountSort(int* a, int n)
{assert(a);int min = a[0];int max = a[0];for (int i = 0; i < n; ++i){if (a[i] > max){max = a[i];}if (a[i] < min){min = a[i];}}int range = max - min + 1;  //0  9 共十个数 9-0 +1 == 10int* countArr=(int*)malloc(sizeof(int) * 10);memset(countArr, 0, sizeof(int)*range);//统计次数for (int i = 0; i < n; ++i){countArr[a[i] - min]++;   //相对位置}//排序int index = 0;for (int j = 0; j< range; ++j){while (countArr[j]--){a[index++] = j + min;}}free(countArr);
}

计数排序总结：

计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。、序列中最大值和最小值之间的差值不能过大，太大会造成空间浪费，要求序列中存在的元素是整数，因为要作为统计数组的下标。

稳定性：稳定

排序总结：