文章链接:https://codemouse.online/archives/2020-05-17-22-08-18
插入排序
// 插入排序,从大到小
void sortInsert(int* arr, int len)
{
int temp = 0;
for ( int i = 1,j =0; i < len ; i++)
{
temp = arr[i];
for (j = i-1; j >= 0 && arr[j] < temp; --j)
{
arr[j+1] = arr[j];
}
arr[j+1] = temp;
}
}
希尔排序
// 希尔排序(插入排序直接改进,加入一个步长机制)
void sortShell(int* arr, int len)
{
int temp = 0;
// k为步长
for(int k = len/2; k>0; k/=2)
{
for ( int i = k,j =0; i < len ; i+=k)
{
temp = arr[i];
for (j = i-k; j >= 0 && arr[j] < temp; j-=k)
{
arr[j+k] = arr[j];
}
arr[j+k] = temp;
}
}
}
快速排序
void quick(int *arr,int start, int end)
{
if(start>=end) return;
// 设置基准key
int key = arr[start];
int l = start;
int h = end;
while(l<h)
{
while(l<h && key >= arr[h])
h--;
arr[l] = arr[h];
while(l<h && key <= arr[l])
l++;
arr[h] = arr[l];
}
arr[l] = key;
// 分割数组(逻辑上)
quick(arr,start,l-1);
quick(arr,l+1,end);
}
// 快速排序
void sortQuick(int *arr, int len)
{
quick(arr,0,len-1);
}
归并排序
void merge(int *arr, int *temp, int begin, int mid, int end)
{
int left = begin;
int right = mid+1;
int len = end - begin + 1;
for(int i = 0; i < len ; i++)
{
if(left > mid){ // 左边已经全部取完
temp[i] = arr[right++];
}else if(right > end){ // 右边已经全部取完
temp[i] = arr[left++];
}else if(arr[left] < arr[right]){ // 从大到小排序
temp[i] = arr[right++];
}else{
temp[i] = arr[left++];
}
}
// 将辅助数组的数据写回
memcpy(arr+begin,temp, sizeof(int)*len);
}
void splitMerge(int *arr,int *temp, int begin, int end)
{
if(begin>=end) return;
int mid = (begin+end)/2;
// 拆分数组
splitMerge(arr,temp, begin,mid);
splitMerge(arr,temp, mid+1,end);
// 合并数组
merge(arr, temp, begin,mid, end);
}
// 归并排序
void sortMerge(int *arr, int len)
{
// 归并排序是一个外排序,需要数组辅助
int *temp = (int *)malloc(sizeof(int)*len);
splitMerge(arr,temp,0,len-1);
free(temp);
}
实例演示
void printArr(int *arr, int len)
{
for (int i = 0 ; i < ARRNUM ; i++ )
{
printf("%d ",arr[i]);
}
printf("\n");
}
void main()
{
int arr[ARRNUM]={234,52,123,5,346,32,5345,6345,131,35};
int arr1[ARRNUM];
int arr2[ARRNUM];
int arr3[ARRNUM];
memcpy(arr1,arr,ARRNUM*sizeof(int));
memcpy(arr2,arr,ARRNUM*sizeof(int));
memcpy(arr3,arr,ARRNUM*sizeof(int));
sortInsert(arr, ARRNUM);
printArr(arr, ARRNUM);
sortShell(arr1, ARRNUM);
printArr(arr1, ARRNUM);
sortQuick(arr2, ARRNUM);
printArr(arr2, ARRNUM);
sortMerge(arr3, ARRNUM);
printArr(arr3, ARRNUM);
}