直接插入排序，快速排序，归并排序,堆排序，基数排序，计数排序。

#include <stdlib.h> #include "sort_num.h" int random_num(int *num, int length){ int i; for(i=0 ; i<length; i++){ num[i] = rand()%65535+1; } return 1; } int insert_sort(int *num, int length){ int i; int j; int temp; for(i=1; i<length; i++){ temp = num[i]; j = i-1; while((j>=0)&&(num[j]>temp)){ num[j+1] = num[j]; j--; } num[j+1] = temp; } return 1; } void merge(int *num, int head, int middle, int tail){ int left_len = middle-head+1; int right_len = tail-middle; int k; int *left = (int *)malloc(sizeof(int)*left_len); int *right = (int *)malloc(sizeof(int)*right_len); int i; int j; for(i=0; i<left_len; i++){ left[i] = num[head+i]; } for(j=0; j<right_len; j++){ right[j] = num[middle+j+1]; } i = j = 0; for(k=head; k<=tail; k++){ if(i<left_len&&j<right_len){ if(left[i]<right[j]) num[k] = left[i++]; else num[k] = right[j++]; } else if(i<left_len) num[k] = left[i++]; else num[k] = right[j++]; } free(left); free(right); return ; } int merge_sort(int *num, int head, int tail){ int middle; if(head<tail){ middle = (head+tail)/2; merge_sort(num,head,middle); merge_sort(num, middle+1, tail); merge(num, head, middle, tail); } return 1; } int max_heapify(int *num, int i, int length){ int left = 2*i+1; int right = 2*i+2; int largest; if((left<length)&&(num[left]>num[i])) largest = left; else largest = i; if((right<length)&&(num[right]>num[largest])) largest = right; if(largest!=i){ num[i] = num[i]+num[largest]; num[largest] = num[i]-num[largest]; num[i] = num[i]-num[largest]; max_heapify(num, largest, length); } return 1; } int build_max_heap(int* num, int length){ int i; for(i=length/2-1; i>=0; i--){ max_heapify(num, i, length); } return 1; } int heap_sort(int *num, int length){ int i; build_max_heap(num, length); for(i=length-1; i>=0; i--){ if(i!=0){ num[i] = num[0]+num[i]; num[0] = num[i]-num[0]; num[i] = num[i]-num[0]; } length--; max_heapify(num, 0 ,length); } return 1; } int partition(int *num, int head, int tail){ int i,j; int temp; i=head-1; for(j=head; j<tail; j++){ if(num[j]<num[tail]){ i++; temp = num[j]; num[j] = num[i]; num[i] = temp; } } i++; temp = num[tail]; num[tail] = num[i]; num[i] = temp; return i; } int quick_sort(int *num, int head, int tail){ int q; if(head<tail){ q= partition(num, head, tail); quick_sort(num, head, q-1); quick_sort(num, q+1, tail); } return 1; } int counting_sort(int *des, int length, int max){ int *count = (int *)malloc(sizeof(int)*(max+1)); int *src = (int *)malloc(sizeof(int)*length); int i; for(i=0; i<=max; i++){ count[i] = 0; } for(i=0; i<length; i++){ src[i] = des[i]; count[src[i]]++; } for(i=1; i<=max; i++){ count[i] += count[i-1]; } for(i=length-1; i>=0; i--){ des[count[src[i]]-1] = src[i]; count[src[i]]--; } free(count); free(src); return 1; } int counting_sort_digit(int *des, int length, int digit){ int *count = (int *)malloc(sizeof(int)*2); int *src = (int *)malloc(sizeof(int)*length); int *key = (int *)malloc(sizeof(int)*length); int i; count[0] = count[1] = 0; for(i=0; i<length; i++){ src[i] = des[i]; key[i] = ((des[i]&(1<<digit))>>digit); count[key[i]]++; } count[1] += count[0]; for(i=length-1; i>=0; i--){ des[count[key[i]]-1] = src[i]; count[key[i]]--; } free(count); free(src); return 1; } int radix_sort(int *num, int length, int low, int high){ int i; for(i=low; i<=high; i++){ counting_sort_digit(num, length, i); } return 1; }