希尔排序
- 根据不同的步长，步长前面的值与步长后面的值做比较
- 小的放前面，大的放后面
归并排序
- 将数组整体，不断的递归砍半
- 直到数组被砍成只有2个元素的时候，进行排序，再做合并操作
快速排序
- 定义哨兵（例如左边第一个）key，标志一个数字，左边的开始的索引 i，右边开始的索引 j
- 从不是哨兵的一端开始往中间走（例如此处是从右向左走），若数字小于 哨兵，则把 对应 i 的位置 赋值 data[j]
- 从左往右走，若数字大于key，则把 对应 j 的位置 赋值 data[i]
- 最后把 key赋值给 data[i]
- 此时 ，data[i] 左边的数字都是小于 data[i] 的， 右边的数字都是大于data[i]的
- 开始左边部分的数字进行递归
- 右边部分的数字进行递归
#include <stdio.h> #define ARRAY_LENGTH 12 //希尔排序 void shell_sort(int *data,int length) { int gap = 0; int i ,j; int tmp; for(gap = length/2;gap>=1;gap = gap/2){ for(i = gap;i<length;i++){ tmp = data[i]; for(j = i-gap; j>=0 && data[j]>tmp ; j = j-gap){ data[j+gap] = data[j]; } data[j+gap] = tmp; } } } //归并排序 -- 需要用到临时数组进行转换 void merge(int *data,int *tmp,int start,int mid,int end) { int i = start; int j = mid+1; int k = start; while(i<=mid && j<=end) { if(data[i] <=data[j]) { tmp[k++] = data[i++]; } else { tmp[k++] = data[j++]; } } //判断是否i还有剩余或者j还有剩余 while(i<=mid) { tmp[k++] = data[i++]; } while(j<=end) { tmp[k++] = data[j++]; } for(i = start;i<=end;i++) { data[i] = tmp[i]; } return ; } void merge_sort(int *data,int *tmp,int start,int end) { if(start < end) { int mid = start + (end - start)/2; merge_sort(data,tmp,start,mid); merge_sort(data,tmp,mid+1,end); merge(data,tmp,start,mid,end); } return ; } //快速排序 -- 定义哨兵的方式 void sort(int *data,int left,int right) { if(right <= left) return ; int key = data[left]; int i = left; int j = right; while(i < j) { while(i<j && data[j] >= key) j--; data[i] = data[j]; while(i<j && data[i] <= key) i++; data[j] = data[i]; } data[i] = key; sort(data,left,i-1); sort(data,i+1,right); } void quick_sort(int *data,int length) { sort(data,0,length-1); } int main(int argc,char *argv[]) { int arr[ARRAY_LENGTH] = {23, 64, 24, 12, 9, 16, 53, 57, 71, 79, 87, 97}; #if 0 shell_sort(arr,ARRAY_LENGTH); #elif 0 int tmp[ARRAY_LENGTH] = {0}; merge_sort(arr,tmp,0,ARRAY_LENGTH-1); #else quick_sort(arr,ARRAY_LENGTH); #endif for(int i = 0;i<ARRAY_LENGTH;i++){ printf("%3d",arr[i]); } printf("\n"); }
