排序算法总结—时间复杂度O(nlogn)—希尔/堆排序/快排/归并
希尔排序
有一段间隔的排序，可以逐个子表进行排序，然（例如王道）都给出便于计算机进行连续访问的程序算法，即依次按元素比较不同子表进行子表的调整。
时间复杂度O(n^1.3) 最坏情况下n方
空间复杂度O（1）
不稳定
适用于线性表为顺序存储。
数组排序例题：给你一个整数数组nums，请你将该数组升序排列。
/*** Note: The returned array must be malloced, assume caller calls free(). */ //希尔 int* sortArray(int* nums, int numsSize, int* returnSize){ // int *returns = (int *)malloc(sizeof(int )* numsSize); int temp,index;//暂存当前比较的数组元素 for(int dk = numsSize/2;dk > 0;dk /= 2) { // printf("%d ",dk); for(int i = dk;i < numsSize;i++) { // printf("%d",nums[i-dk]); if(nums[i] < nums[i-dk]) { temp = nums[i]; index = i-dk; while(index >= 0 && temp < nums[index]) { // printf("%d ",index); nums[index+dk] = nums[index]; index -= dk; } nums[index+dk] = temp; // printf("%d",nums[index+dk]); } } } // for(int k = 0;k < numsSize;k++) // { // returns[k] = nums[k]; // } *returnSize = numsSize; return nums; }
相对名次例题
给出N名运动员的成绩，找出他们的相对名次并授予前三名对应的奖牌。前三名运动员将会被分别授予 “金牌”，“银牌” 和“ 铜牌”（“Gold Medal”, “Silver Medal”, “Bronze Medal”）。
(注：分数越高的选手，排名越靠前。)
`示例 1:
输入: [5, 4, 3, 2, 1]
输出: [“Gold Medal”, “Silver Medal”, “Bronze Medal”, “4”, “5”]
解释: 前三名运动员的成绩为前三高的，因此将会分别被授予 “金牌”，“银牌”和“铜牌” (“Gold Medal”, “Silver Medal” and “Bronze Medal”).
余下的两名运动员，我们只需要通过他们的成绩计算将其相对名次即可。
提示:
1.N 是一个正整数并且不会超过 10000。
2.所有运动员的成绩都不相同。
/*** Note: The returned array must be malloced, assume caller calls free().***/ char ** findRelativeRanks(int* score, int scoreSize, int* returnSize){ *returnSize = scoreSize; int a[scoreSize]; for(int m = 0;m < scoreSize;m++) { a[m] = score[m]; } char **returns = (char **)malloc(sizeof(char*)*scoreSize); int temp,index; for(int dk = scoreSize/2;dk > 0;dk /= 2) { for(int i = dk;i < scoreSize;i++) { if(score[i-dk] < score[i]) { temp = score[i]; index = i-dk; while(index >= 0 && temp > score[index]) { score[index+dk] = score[index]; index -= dk; } score[index+dk] = temp; } } } // printf("%c",(char)(5+'0')); for(int k = 0;k < scoreSize;k++) { for(int m = 0;m < scoreSize;m++) { if(a[k] == score[m]) { if(m == 0) returns[k] = "Gold Medal"; else if(m == 1) returns[k] = "Silver Medal"; else if(m == 2) returns[k] = "Bronze Medal"; else { returns[k] = (char*)malloc(sizeof(char)*10); sprintf(returns[k],"%d",m+1) ; // char m = (k+'0'); // returns[k] = m; } break; } } } return returns; }
堆排序
适合关键字超级多的情况。比如一万个数挑出前100个最大最小值。
在建立大根堆或小根堆情况下，递归排序，提出根结点，继续建立大根堆或小根堆。
时间复杂度：O（nlogn）
空间复杂度：O（1）
不稳定
最小的k个数
输入整数数组arr，找出其中最小的k个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。**
/** * Note: The returned array must be malloced, assume caller calls free(). */ //堆排序 void heapAdjust(int a[],int k,int len) { int temp = a[k]; for(int j = k*2 ;j <= len;j *= 2)//第2个结点-1 = 下标 { if(j < len && a[j] > a[j+1]) { j++; } if(a[j] >= temp) break; else { a[k] = a[j]; k = j; } } a[k] = temp; } void buildheap(int a[],int len) { for(int j = len/2;j > 0;j--) { heapAdjust(a,j,len); } } void swap(int *a,int *b) { int temp = *a; *a = *b; *b = temp; } int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize){ // int * a = (int *)malloc(sizeof(int )*(arrSize+1)); int a[arrSize+1]; // arr[arrSize] = (int *)malloc(sizeof(int )*1); // arr[arrSize] = 1; // printf("%d",arr[arrSize]); int m = 1; for(int j = 0;j < arrSize;j++) { a[m++] = arr[j]; // printf("%d",a[m-1]); } *returnSize = k; int *returns = (int *)malloc(sizeof(int) * k); buildheap(a,arrSize); for(int i = 0,x = arrSize;i < k;i++,x--) { returns[i] = a[1]; // printf("%d",a[1]); // printf("%d ",a[x]); swap(&a[1],&a[x]); // printf("%d",a[1]); // printf("%d ",a[x]); heapAdjust(a,1,x-1); // printf("m%dm",returns[i]); } return returns; }
快速排序
以某一个元素为枢轴，以轴旋转，比轴小的在左侧，比轴大的在右侧。
每次排序会有一个位置元素回到确定的位置。（理想下，第k轮，排好2的k-1次方个数）
该代码重要的是分区思想的代码，注意边界条件。
1⃣️最简单的思路是：从 left 开始，遇到比基数大的数，就交换到数组最后，并将 right 减一，直到 left 和 right 相遇，此时数组就被分成了左右两个区域。再将基数和中间的数交换，返回中间值的下标即可。
2⃣️双指针：从 left 开始，遇到比基数大的数，记录其下标；再从 right 往前遍历，找到第一个比基数小的数，记录其下标；然后交换这两个数。继续遍历，直到 left 和 right 相遇。然后就和刚才的算法一样了，交换基数和中间值，并返回中间值的下标。
（我猜我们会考双轴快排）
时间复杂度：O（nlogn）
空间复杂度：最好情况O（logn） 有递归存在，栈的深度为logn
不稳定
还是用排序数组的题
这个敲的很顺手！
/** * Note: The returned array must be malloced, assume caller calls free(). */ int* sortArray(int* nums, int numsSize, int* returnSize){ if(numsSize == 0) return nums; *returnSize = numsSize; quicksort(nums,0,numsSize-1); return nums; } void quicksort(int a[],int start,int end) { if(start >= end) return; int mid = partition(a,start,end); quicksort(a,start,mid-1); quicksort(a,mid+1,end); } int partition(int a[],int start,int end) { int temp = a[start]; int left = start + 1; int right = end; while(left < right) { while(left < right && a[left] <= temp) left++; // while(left < right && a[right] >= temp) right--; if(left != right) { swap(a,left,right); // left++; right--; } } if(left == right && a[right] > temp) right--; if(right != start) swap(a,start,right); return right; } void swap(int a[],int x,int y) { int t = a[x]; a[x] = a[y]; a[y] = t; }
归并排序
两个有序子表合并，整个归并排序需要进行logn向上取整趟。
先拆开，再两两合并。
时间复杂度：O（nlogn）
空间复杂度：O（n）需要一个辅助数组的空间
稳定！！终于稳定啦！撒花🎉
逆序对
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
这道题太好了！每次看每次都看明白，下一次都又，啥啊，这是什么啊？
！！划重点，敲黑板🤏
对于分成1个1个子表开始合并时，若后边的元素要放入数组中，就证明该元素比前边元素都小，形成了前面剩下元素个逆序对，依次记录📝，可得总和。
int reversePairs(int* nums, int numsSize){ int count = 0; int *com = (int *)malloc(sizeof(int)*numsSize); // for(int i = 0; i < numsSize;i++) // { // com[i] = nums[i]; // } count = mergesort(nums,com,0,numsSize-1,count); return count; } int mergesort(int a[],int com[],int low,int high,int count) { // int count = 0; if(low < high) { int mid = (low+high)/2; count = mergesort(a,com,low,mid,count); count = mergesort(a,com,mid+1,high,count); // printf("a%d ",count); count = merge(a,com,low,mid,high,count); // printf(" %da",count); } return count; } int merge(int a[],int com[],int low,int mid,int high,int count) { // int count = 0; // int *com = (int *)malloc(sizeof(int)*); // printf("b%d",count); for(int i = low; i <= high;i++) { com[i] = a[i]; } int i,j,k; for(i = low,j = mid+1,k = low;i <= mid && j <= high;k++) { if(com[i] <= com[j]) { a[k] = com[i]; i++; } else { a[k] = com[j]; j++; count += mid-i+1; //每一次后边的小放到前面就形成了前一个数组所剩元素数量的逆序对 } // printf("%db",count); } while(i <= mid) a[k++] = com[i++]; while(j <= high) a[k++] = com[j++]; return count; }
好的！我会了，我一定会这四种了！冲冲冲👌
