有一段间隔的排序，可以逐个子表进行排序，然（例如王道）都给出便于计算机进行连续访问的程序算法，即依次按元素比较不同子表进行子表的调整。
数组排序例题：给你一个整数数组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个最大最小值。
在建立大根堆或小根堆情况下，递归排序，提出根结点，继续建立大根堆或小根堆。
最小的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 相遇。然后就和刚才的算法一样了，交换基数和中间值，并返回中间值的下标。
（我猜我们会考双轴快排）
/**
* 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向上取整趟。
先拆开，再两两合并。
