十大排序算法

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-riZ9z3wf-1678258189998)(null)]

排序算法的稳定性：在具有多个相同关键字的记录中，若经过排序这些记录的次序保持不变，说排序算法是稳定的。

插入排序O(n²)

• 直接插入排序

  动画演示如图：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-g8yWt978-1678258189738)(null)]

代码如下：

void Straight_Insertion_Sort(int a[],int length){for (int i = 1;i < length;i++) {if (a[i]= 0;j--) {a[j + 1] = a[j];if (a[j] < temp) {a[j + 1] = temp;break;}if (j == 0 && a[j] > temp) {a[j] = temp;}}}}
}

• 折半插入排序

  主要分为查找和插入两个部分，图片演示：

  [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NGdwZzKt-1678258189775)(null)]

  代码如下：

  void Binary_Insert_Sort(int a[],int length) {int low, high, mid;int i, j,temp;for ( i = 1;i < length;i++) {low = 0;high = i - 1;temp = a[i];while (low<=high) {mid = (low + high) / 2;if (temp high;j--) {a[j + 1] = a[j];}a[j + 1] = temp;}//for(i)
  

冒泡排序O(n²)

思路：两两比较元素，顺序不同就交换

图解：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-oaXan5Ej-1678258195664)(null)]

代码：

void Bubble_Sort(int a[],int length) {for (int i = 0;i < length - 1;i++) {for (int j = 0;j a[j+1]) {int temp = a[j];a[j] = a[j +1];a[j+1] = temp;}}}
}

选择排序O(n²)

思路：每一次从待排序的数据元素中选择最小（最大）的一个元素作为有序的元素。如果是升序排序，则每次选择最小值就行，这样已经排好序的部分都是生序排序选择排序是不稳定的，比如说（55231这种情况，两个5的相对顺序会变）

图解：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-V6t6QV9b-1678258189910)(null)]

代码：

void Select_Sort(int a[],int length) {for (int i = 0;i < length - 1;i++) {int min_index = i;for (int j = i+1;j < length;j++) {if (a[min_index]>a[j]) {min_index = j;}}//for jif (i!=min_index) {int temp = a[i];a[i] = a[min_index];a[min_index] = temp;}}//for i
}

希尔排序—缩小增量排序O(nlogn)

思路：

希尔排序又叫缩小增量排序，使得待排序列从局部有序随着增量的缩小编程全局有序。当增量为1的时候就是插入排序，增量的选择最好是531这样间隔着的。

其实这个跟选择排序一样的道理，都是不稳定的比如下图7变成9的话，就是不稳定的。

图解：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-MFDsQWDw-1678258195700)(null)]

代码：

void Shell_Sort1(int a[], int length) {//首先定义一个初始增量，一般就是数组长度除以2或者3int gap = length / 2;while (gap >= 1) {for (int i = gap;i < length;i++) {int temp = a[i];int j = i;while (j >= gap&&temp 0; gap /= 2)for (i = gap; i < n; i++)/*j>gap之后，j前面的可以重新比较依次保证j前面间隔gap的也是有序的*/for (j = i - gap; j >= 0 && a[j] > a[j + gap]; j -= gap)Swap(a[j], a[j + gap]);
}

快速排序O(nlogn)

思路：快排的核心叫做“基准值“，小于基准值的放在左边，大于基准值的放在右边。然后依次递归。基准值的选取随机的，一般选择数组的第一个或者数组的最后一个，然后又两个指针low和high

图解：基准值就是第一个元素

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-oMPzPYDy-1678258195792)(null)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Hd75UZnt-1678258195626)(null)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-9cg43CQr-1678258189634)(null)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-C02wROnH-1678258189945)(null)]

1）设置两个变量I、J，排序开始的时候：I=0，J=N-1；

2）以第一个数组元素作为关键数据，赋值给 key ，即 key =A[0]；

3）从J开始向前搜索，即由后开始向前搜索（J=J-1即J–），找到第一个小于 key 的值A[j]，A[j]与A[i]交换；

4）从I开始向后搜索，即由前开始向后搜索（I=I+1即I++），找到第一个大于 key 的A[i]，A[i]与A[j]交换；

5）重复第3、4、5步，直到 I=J； (3,4步是在程序中没找到时候j=j-1，i=i+1，直至找到为止。找到并交换的时候i， j指针位置不变。另外当i=j这过程一定正好是i+或j-完成的最后另循环结束。）

代码：

//快速排序 需要两个函数配合
int Quick_Sort_GetKey(int a[],int low,int high) {int temp = a[low];while (low=temp) {high--;}//当a[high]

//index是第一个非叶子节点的下标（根节点）
//递归的方式构建
void Build_Heap(int a[],int length,int index){int left = 2 * index + 1;  //index的左子节点int right = 2 * index + 2;//index的右子节点int maxNode = index; //默认当前节点是最大值，当前节点indexif (lefta[maxNode]) {maxNode = left;}if (righta[maxNode]) {maxNode = right;}if (maxNode!=index) {int temp = a[maxNode];a[maxNode] = a[index];a[index] = temp;Build_Heap(a,length,maxNode);}}
void Heap_Sort(int a[],int length) {// 构建大根堆（从最后一个非叶子节点向上）//注意，最后一个非叶子节点为(length / 2) - 1for (int i = (length / 2) - 1;i >= 0;i--) {Build_Heap(a, length, i);}for (int i = length - 1;i >= 1;i--) {//交换刚建好的大顶堆的堆顶和堆末尾节点的元素值，int temp = a[i];a[i] = a[0];a[0] = temp;//交换过得值不变，剩下的重新排序成大顶堆Build_Heap(a,i,0);} 
}

//分治思想，先逐步分解成最小(递归)再合并
//归并
void Merge(int a[],int low,int mid,int high) {int i = low;int j = mid + 1;int k = 0;int *temp = new int[high - low + 1];while (i<=mid&&j<=high) {if (a[i]<=a[j]) {temp[k++] = a[i++];}else {temp[k++] = a[j++];}}//while (i

void Count_Sort(int a[],int length) {//得到待排序的最大值int max = a[0];int i=0;while ( i a[i + 1]) ? a[i] : a[i + 1];i++;}int *countArray = new int[max + 1]{0};int *temp = new int[length];for (int i = 0;i < length;i++) {countArray[a[i]]++;}//!!!这一步的思想特别重要，在非比较排序中for (int i = 1;i < max+1;i++) {countArray[i] += countArray[i - 1];}//反向遍历for (int i = length - 1;i >= 0;i--) {temp[countArray[a[i]]-1] = a[i];countArray[a[i]]--;}for (int i = 0;i < length;i++) {a[i] = temp[i];}delete[] countArray;delete[] temp;
}

int Get_Max_Digits(int a[],int length) {int max = a[0];int i = 0;while (i a[i + 1]) ? a[i] : a[i + 1];i++;}int b = 0;//最大值的位数while (max>0) {max = max / 10;b++;}return b;
}
//切记！桶子只能是十个，是定死的
void Radix_Sort(int b[],int length) {int d = Get_Max_Digits(b, length);//得到最大值的位数int * temp = new int[length];//开辟一个和原数组相同的临时数组//根据最大值的位数进行排序次数循环int radix = 1;for (int i = 0;i < d;i++) {//每次把数据装入桶子前先清空countint count [10] = { 0 }; //计数器 每次循环都清零for (int j = 0;j < length;j++) {//统计尾数为0-9的个数，一次是个十百千....位int tail_number = (b[j]/radix)%10;count[tail_number]++;//每个桶子里面的个数 }//桶中的每一个数的位置一次分配到temp数组中，先找到位置for (int j = 1;j < 10;j++) {count[j] += count[j - 1];}//分配到temp中排序后的位置for (int j = length - 1;j >= 0;j--) {int tail_number = (b[j] / radix) % 10;temp[count[tail_number] - 1] = b[j];count[tail_number]--;}//赋值for (int j = 0;j < length;j++) {b[j] = temp[j];}radix *= 10;}//for(int i)delete[] temp;
}

void bucketSort(int arr[], int len) {// 确定最大值和最小值int max = INT_MIN; int min = INT_MAX;for (int i = 0; i < len; i++) {if (arr[i] > max) max = arr[i];if (arr[i] < min) min = arr[i];}// 生成桶数组// 设置最小的值为索引0，每个桶间隔为1int bucketLen = max - min + 1;// 初始化桶int bucket[bucketLen];for (int i = 0; i < bucketLen; i++) bucket[i] = 0;// 放入桶中int index = 0;for (int i = 0; i < len; i++) {index = arr[i] - min;bucket[index] += 1;}// 替换原序列int start = 0;for (int i = 0; i < bucketLen; i++) {for (int j = start; j < start + bucket[i]; j++) {arr[j] = min + i;}start += bucket[i];}
}