数据结构：八大排序

数据结构：八大排序

目录

排序

一、插入排序

二、希尔排序

--预排序

三、选择排序

四、冒泡排序

五、堆排序

六、快速排序

--快速排序优化

--递归该非递归

七、归并排序

--递归改非递归

八、计数排序

---

排序

一、插入排序

时间复杂度：O（N^2）(最坏)

思想：把待排的序列逐个插入到已经排好的有序序列中，直到排完，得到一个新的有序序列

1.把第一个元素当作有序，往后插入一个数据进行排序，得到2个元素有序序列

2.前2个元素已经有序，再往后插入一个数据进行排序，得到3个元素的有序序列

3.前3个元素已经有序，再往后插入一个数据进行排序，得到4个元素的有序序列

......

4.直到排序完，得到有序的序列

一次排序：

 代码：

//插入排序
void InsertSort(int* array, int length)
{assert(array);for (int i = 0; i < length-1; i++){int end = i;//前一个位置int tmp = array[end + 1];//当前位置while (end >= 0){// tmp小,向后移动元素if (tmp < array[end]){array[end + 1] = array[end]; end--;}//不处理else{break;}}// 找到比cur小的，放其后面array[end + 1] = tmp; }
}

效果：

二、希尔排序

思路：

1.预排序

2.直接插入排序

基本思想：通过将数组分割成多个子序列来改善插入排序的效率，然后逐步减小子序列的间隔，直到最终完成排序。

步骤：1.选择间隔  2.对子序列进行插入排序  3.不断缩小间隔   4.最终排序(间隔为1)

原因：

对于直接插入排序：所给的序列越接近有序，其时间复杂度越低

我们可以先对其进行预排序，让其接近有序序列，最后再进行直接插入排序

--预排序

补充：

gap越大，大的数字越快到后面，小的数字越快到前面 ，序列越不接近有序

gao越小，大的数字越慢到后面，小的数字越慢到前面，序列越接近有序

一次子序列排序代码：(与直接插入排序差不多，改的是间隔)

这里注意i的结束位置为n-gap-1，由于tmp记录的是子序列的后一个元素，需要控制其不越界

//一次子序列排序
void ShellSort(int* a, int n) 
{for (int i = 0; i < n - gap; i++){int end = i;int tmp = a[end + gap];//记录子序列中后一个数的值while (end >= 0){//tmp比前面的数字小，往后移动数据if (tmp < a[end]){a[end + gap] = a[end];end -= gap;//继续找前面的一个数字}else{//找完结束break;}}//将tmp放在正确的位置a[end + gap] = tmp;}
}

一次预排序，需要将所有子序列都排序一遍

1.直接嵌套一层循环，给出子序列

子序列的组数：gap

这里可以看到可以划分为gao组子序列

 代码：

	for (int j = 0; j < gap; j++) {}

把之前代码嵌套进去即可

2.子序列交替进行排序（不新增加循环嵌套）

代码：

//for (int i = 0; i <n - gap ; i +=gap) 改为for (int i = 0; i <n - gap ; i++){}

这样可以达到交替的效果：

一次预排序

//一次预排序
void ShellSort(int* a, int n) 
{//1.选取间隔gap = 3;for (int i = 0; i < n-gap; i++){int end = i;int tmp = a[end + gap];//记录子序列中后一个数的值while (end >= 0){//tmp比前面的数字小，往后移动数据if (tmp < a[end]){a[end + gap] = a[end];end -= gap;//继续找前面的一个数字}else{//找完结束break;}}//将tmp放在正确的位置a[end + gap] = tmp;}
}

我们先给gap赋值为n

每一次预排序，gap除以3，为了确保gap最后为1，再后面加上1

希尔排序：

//希尔排序
void ShellSort(int* a, int n) 
{//1.预排序int gap = n;//当间隔为1时结束while (gap > 1) {//选取间隔gap = gap/3 + 1;//一次预排序for (int i = 0; i < n-gap; i++){int end = i;int tmp = a[end + gap];//记录子序列中后一个数的值while (end >= 0){//tmp比前面的数字小，往后移动数据if (tmp < a[end]){a[end + gap] = a[end];end -= gap;//继续找前面的一个数字}else{//找完结束break;}}//将tmp放在正确的位置a[end + gap] = tmp;}}//直接排序InsertSort(a,n);}

效果：

三、选择排序

时间复杂度：O（N^2）

思路：

1.遍历找出最小的元素（排升序）

2.将最小的元素放在序列起始位置

3.缩小范围，重复1 2

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

注：这里我们优化一下：

1.一次性将最小值和最大值找出

2.分别放在最左边和最右边

3.缩小范围，重复1，2

代码：

//选择排序
void SelectSort(int* a, int n) 
{int left, right, maxi, mini;left = 0, right = n - 1;while (left < right) {mini = maxi = left;//1.找最大值和最小值的位置for (int i = left+1; i <= right; i++){//找最小值if (a[i] < a[mini]) mini = i;//找最大值if (a[i] > a[maxi]) maxi = i;}//2.将最小值放在最左边，将最大值放在最右边swap(&a[left], &a[mini]);//排查一下最大值的位置和起始位置重复if (maxi == left) maxi = mini;swap(&a[right], &a[maxi]);//3.缩小范围，重复12left++;right--;}}

注：需要检查maxi是否和leff重叠

 效果：

四、冒泡排序

时间复杂度：O{N^2}

思想：将序列中的数字两两比较，若前面的数字大于后面的数字就交换，这样经过一轮冒泡，最大的数字就被放在了最后面

思路：

1.将序列中的数字两两比较，判断是否交换

2.缩小范围，重复1

代码：

//冒泡排序
void BubbleSort(int* a, int n) 
{//每冒泡一轮就将最大的数字放在最最后面//10个数字冒泡9次就有序了for (int i = 0; i < n-1; i++) {int flag = 0;for (int j = 0; j < n - i- 1; j++) {//若a[j]>a[j+1]就交换if (a[j] > a[j + 1]) {swap(&a[j],&a[j+1]);flag = 1;}}//说明已经有序,不需要再排序if (flag == 0) {break;}}
}

 效果：

五、堆排序

时间复杂度：N*logN

思路：

1.建堆

2.将堆顶的元素与堆尾的元素交换

3.将剩下N-1个元素进行堆的调整（这里我们从堆顶开始向下调整）

这样，进行一轮23，就有一个元素从堆尾开始排好序（从大到小或从小到大）

 1.建堆

• 升序：建大堆
• 降序：建小堆

方式1：向上建堆，时间复杂度N*logN（从最后一个节点开始向上建堆）

	//1.建堆（向上建堆）for (int i = n-1;i > 0; i--) {AdjustUp(a,i);}

方式2：向下建堆，时间复杂度N（从第一个非叶子节点开始向下建堆）

	//2.建堆（向下建堆,从第一个非叶子节点开始）for (int i = (n - 1 - 1) / 2; i > 0; i--) {AdjustDown(a,n,i);}

补充：AdjustUp，AdjustDown

//向上调整
void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;while (child > 0){//大根堆if (a[child] > a[parent])//if (a[child] > a[parent]){swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}//由上往下调整
void AdjustDown(HPDataType* a, int size, int parent)
{int child = parent * 2 + 1;//找到孩子节点//3.当走到叶子节点的时候结束调整while (child < size){//1.找到较大孩子节点，并防止没有右孩子越界if (child + 1 < size && a[child] < a[child + 1]){child++;}//2.判断是否需要调整if (a[child] > a[parent]){swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

2.利用堆删除思想排序

--假设建立的为小堆：

       进行第一次23，第一小的元素被放在堆尾

       进行第二次23，第二小的元素被放在堆倒数第二个位置

       ......

       进行第size次23，全部元素按照从大到小顺序排序好   
 

//堆排序
void HeapSort(int* a, int n)
{//1.建堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}//将堆顶的元素和最后一个元素交换//从该位置开始向下调整//若建立的是小根堆，排出的顺序为降序：最小的先放在了最后面，然后循环找出次小的放其前面//若建立的是大根堆，排出的顺序为升序：最大的先放在了最后面，然后循环找出次大的放其前面int top = 0;int end = n - 1;while (end >= 0){//2.交换swap(&a[top], &a[end]);//3.开始向下调整AdjustDown(a, end, 0);end--;//更新end}
}

 效果：

六、快速排序

时间复杂度：N*logN

思想：先选择一个基准元素，然后将序列分为两组：left，right，一组都比基准元素小，一组都比基准元素大，然后递归地对子数组进行排序，最后将整个数组排序

思路：

1.选择基准元素 ：通常为第一个元素

2.分割数组并重新排列：使得left都是比基准元素小的，right都是比基准元素大的

3.递归排序：将基准元素左边和右边的数组分别递归进行快速排序

4.合并结果：递归排序完成后，就会变得有序

递归排序后能有序的原因： 

1.将大问题拆分为小问题

2.当数组元素个数只有一个或没有的时候，已经排好序了，开始返回

快排代码：

//快速排序
void QuickSort(int* a, int begin, int end) 
{//只有一个或没有元素的时候不用再排序if (begin >= end)return;//排序一次int keyi = PortSort3(a,begin,end);//快排key的左边和右边QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);}

1.hoare法代码：

int PortSort1(int* a, int begin, int end) 
{//1.选keyint keyi = begin;int left = begin;int right = end;//2.排序while (left < right) {//right先走，找小while (left<right && a[right] >= a[keyi]) {right--;}//left再走，找大while (left < right && a[left] <= a[keyi]) {left++;}//找到后交换left和rightswap(&a[left],&a[right]);}//3.left和right相遇后，交换key和rightswap(&a[keyi],&a[right]);//更新keyikeyi = right;return keyi;
}

效果：

 2.挖坑法

思路：

保存一下key的值

1.先选择key的位置为坑

2.right找小，找到后把该值填到坑中，此时right的位置为新坑

3.left找大，找到后把该值天到坑中，此时left的位置为新坑

重复23直到left和right相遇，将key值填入到相遇的位置

代码：

//2.挖坑法
int PortSort2(int* a, int begin, int end) 
{//1.保存一下key的值int key = a[begin];int left = begin;int right = end;//选坑位int piti = begin;//开始排序while (left < right) {//right找小，找到填入坑中，其变为新坑while (left<right && a[right] >= key) {right--;}a[piti] = a[right];//填坑piti = right;//right变为新坑//left找大，找到填入坑中，其变为新坑while(left < right && a[left] <= key){left++;}a[piti] = a[left];//填坑piti = left;//left变为新坑}//当left与right相遇，将key填入坑中a[piti] = key;return piti;
}

 效果：

 3.前后指针法

思路：

选定key

1.pre和cur先指向同一位置，cur先走一步

2.cur走的规则：

--cur找到小，找到小后，pre先后走一步，将cur与pre的值交换，然后cur向后走一步

--cur找到大，cur继续向后走一步

注意：若找到小后，++pre和cur的位置相同，则不需要交换（交换自己没有意义）

（无论怎样cur都会向后走一步）

3.当cur走到end结束

4.将pre和key的值交换就完成了一次排序

 代码：

//前后指针
int PortSort3(int* a, int begin, int end) 
{int keyi, pre, cur;keyi = begin;pre = begin;cur = pre + 1;while (cur <= end) {//1.cur找到小，pre向后走，并交换pre，curif (a[cur] <= a[keyi]&&(++pre)!=cur){swap(&a[cur],&a[pre]);}//2.cur比key大，向后走（或处理完）cur++;}//3.找完swap(&a[keyi],&a[pre]);keyi = pre;return keyi;}

--快速排序优化

1.key的取值

key的取值会影响快速排序的效率

1.key的取值越接近中位数，每次递归排序都接近二分，效率更高

2.key的取值越接近最小值，每次递归排序的效率更低，而且冗余栈溢出

对于key的取值：

1.随机取值

2.三数取中法:取中间值 [ 第一个 中间 最后一个 （选不是最大 也不是最小的）]

思路：找到中间值的下标后，将其与begin交换，更改key值

1.取中间值

//获取中间值下标
int GetMidi(int* a, int begin, int end) 
{int max, min, mid,midi;midi = (begin + end) / 2;//找最大值max = a[begin];if (a[midi] > max)   max = a[midi];if (a[end]  > max)   max = a[end];//找最小值min = a[begin];if (a[midi] < min)   min = a[midi];if (a[end]  < min)   min = a[end];//获取中间值(异或)mid = max ^ min ^ a[begin] ^ a[midi] ^ a[end];//返回中间值的下标if (a[begin] == mid)  return begin;if (a[midi] == mid)   return midi;if (a[end] == mid)    return end;
}

2.将其与begin交换

2.小区间优化

当递归划分小区间，区间较小的时候，就不在递归排序这个小区间，用其它排序处理小区间

区间越小，递归调用次数越多 

代码：

//快速排序
void QuickSort(int* a, int begin, int end)
{//只有一个或没有元素的时候不用再排序if (begin >= end)return;//小区间用插入排序处理if (end - begin <= 20) {InsertSort(a + begin,end - begin+1);}//排序一次int keyi = PortSort3(a, begin, end);//快排key的左边和右边QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);}

--递归改非递归

思路：使用栈模仿递归实现（数据结构中的栈是动态开辟的，放在堆中，内存够大）

与层序遍历类似

1.先将数组的left和right入栈

2.再出栈获取left和right，并进行一次快速排序

3.若排序完后，其有子数组，再将子数组入栈

--检查子数组的合法性：begin < keyi -1    keyi+1 >end

4.重复 2 3 直到栈为空 就模拟完快速排序的递归

代码：

//非递归快排
void QuickSortNonR(int* a, int left, int right) 
{ST st;StackInit(&st);//1.先将数组的left和right入栈StackPush(&st,left);StackPush(&st, right);//4.直到栈为空的时候停止while (!StackEmpty(&st)) {//2.出栈进行一次快排int right = StackTop(&st);StackPop(&st);int left = StackTop(&st);StackPop(&st);int keyi = PortSort3(a, left, right);//3.检查其快排一次后有没有子数组，有就入栈if (left < keyi - 1){StackPush(&st, left);StackPush(&st, keyi - 1);}if (keyi + 1 < right){StackPush(&st, keyi + 1);StackPush(&st, right);}}StackDestory(&st);}

 效果：

七、归并排序

时间复杂度：N*logN

基本思想：先将一个待排序的数组分成两个较小的子数组，然后分别对这两个子数组进行排序，最后将排好序的子数组合并成一个有序的数组。

基本步骤：1.拆解         2.排序         3.合并

思路：分治(与后序遍历类似)

1.将待排数组拆解成两个较小的数组，拆解到只剩下一个或没有

2.将拆解的的子数组排序

3.合并排好的子数组

 代码：

//归并排序主要思想
void _MergrSort(int* a, int begin, int end,int* tmp) 
{//1.拆解if (begin >= end) return;int mid = (begin + end) / 2;_MergrSort(a, begin, mid, tmp);_MergrSort(a, mid+1, end, tmp);//2.归并int begin1 = begin, end1 = mid;int begin2 = mid+1, end2 = end;int j = begin;//比较有序数组的大小，谁小就先放进tmp里；while (begin1 <= end1 && begin2 <= end2) {if (a[begin1] < a[begin2]) tmp[j++] = a[begin1++];elsetmp[j++] = a[begin2++];}//若一个数组先拷贝完，将每拷贝玩的数组全部拷贝进tmp中while(begin1 <= end1) tmp[j++] = a[begin1++];while(begin2 <= end2)tmp[j++] = a[begin2++];//将tmp拷贝进a中memcpy(a+begin,tmp+begin,(end-begin+1)*sizeof(int));}

//归并排序
void MergeSort(int* a,int n) 
{//额外开辟一个数组开合并int* tmp = (int*)malloc(n*sizeof(int));if (tmp == NULL) {printf("malloc failn");exit(-1);}//开始归并_MergrSort(a,0,n-1,tmp);//释放tmpfree(tmp);}

效果：

--递归改非递归

思想：手动拆分并排序：

取间隔gap = 1，后依次扩大两倍取归并

 代码：

//归并排序(非递归)
void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int)*n);assert(tmp);int gap = 1;while (gap < n) {// 间距为gap是一组，两两归并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;int index = i;//归并while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2])tmp[index++] = a[begin1++];elsetmp[index++] = a[begin2++];}//若一个数组先拷贝完，将每拷贝玩的数组全部拷贝进tmp中while (begin1 <= end1)tmp[index++] = a[begin1++];while (begin2 <= end2)tmp[index++] = a[begin2++];}//将tmp拷贝给amemcpy(a, tmp, sizeof(int) * n);gap *= 2;}free(tmp);
}

越界问题的处理

这里可以看到，当序列的个数不是2^n个的时候会出现越界

1.改边界值

代码：

// end1 越界，修正
if (end1 >= n)end1 = n - 1;// begin2 越界，第二个区间不存在
if (begin2 >= n)
{begin2 = n;end2 = n - 1;
}// begin2 ok， end2越界，修正end2即可
if (begin2 < n && end2 >= n)end2 = n - 1;

 效果：

当end1越界，begin2越界，将其调整为不存在的区间，下面就不会将其归并

当只用end2越界的时候将其修正，加上归并这一个数字

使其归并完了再拷贝值 

2.越界直接不归并

代码：

//若越界直接不归并
if (begin1 >= n)break;
else if (begin2 >= n)break;
//只有end2越界，只归并一个数
else if (end2 >= n)end2 = n - 1;

效果：

可以选择归并一次就拷贝一次

也可以归并完了再拷贝

八、计数排序

时间复杂度：O（N，MAX-MIN+1）

基本思想：先统计每个元素在待排序数组中出现的次数，然后根据这些统计信息将元素按照顺序放置到输出数组中，

思路：

1.统计元素出现次数（这里额外开辟一个数组）

2.累加次数

3.排序

预备工作：

1.得到数组的最大值和最小值   来决定额外开辟数组tmp空间的大小（max-min+1）

2.使用相对映射来累加元素出现的次数

3.遍历该数组，根据出现的次数排序

相对映射对于负数同理

代码：

计数排序
void CountSort(int* a, int n) 
{//1.获取数组的最大值和最小值来绝对tmp开多大int max = a[0],min = a[0];for (int i = 0; i < n; i++) {if (a[i] > max)max = a[i];if (a[i] < min)min = a[i];}//开辟tmp来记录元素出现的次数int sz = max - min + 1;int* tmp = (int*)calloc(sz,sizeof(int));assert(tmp);//2.相对映射统计次数for (int i = 0; i < n; i++) {tmp[a[i] - min]++;}//3.根据统计的元素排序int j = 0;for (int i = 0; i < sz; i++) {//元素出现多少次，就拷贝过去while (tmp[i]--) {a[j++] = min + i;}}free(tmp);
}

 效果：

 适合：数据集中，范围中等