快速排序

快速排序的执行流程：

(1) 先从数列中取出一个数作为基准数。

(2) 将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

(3)再对左右区间重复第二步，直到各区间只有一个数。

C程序实现：

int *q_sort(int *arr, int left, int right) {    int i, j, t, temp;    if (left >= right) {        return arr;     }    temp = arr[left]; //选择基准值    i = left;    j = right;    while (i != j) {        while (arr[j] >= temp && i

Shell排序

Shell排序是对插入排序的改进。

Shell排序先选取一定的间隔，相差一个间隔的元素视为一个组，在每组内进行插入排序。

然后选取更小的间隔（一般折半）进行插入排序，直至间隔为1。

C程序实现：

int *shell_sort(int *arr, int Len)  {   int i, j, t, gap;   for (gap = Len / 2; gap > 0; gap /= 2) {    for (i = gap; i < Len; i++) {        for ( j = i - gap; j >= 0 && arr[j] > arr[j + gap]; j -= gap) {            t = arr[j];            arr[j] = arr[j+gap];            arr[j+gap] = t;        }    }   }   return arr;}

归并排序

将待排序序列R[0...n-1]看成是n个长度为1的有序序列，将相邻的有序表成对归并，得到n/2个长度为2的有序表；

将这些有序序列再次归并，得到n/4个长度为4的有序序列；如此反复进行下去，最后得到一个长度为n的有序序列。

C程序实现：

void merge_sorting(int *arr, int first,  int last, int *temp) {    int mid = (first + last) / 2;           if (first < last) {        merge_sorting(arr, first, mid, temp);        merge_sorting(arr, mid + 1, last, temp);        merge_array(arr,first, mid, last, temp);    }}void merge_array(int *arr, int first, int mid, int last, int *temp)     {    int i = first, j = mid + 1, k = 0;    int m = mid, n = last;        while (i <= m && j <= n) {        if (arr[i] <= arr[j]) {            temp[k++] = arr[i++];           }        else {            temp[k++] = arr[j++];           }       }    while (i <= m) {        temp[k++] = arr[i++];       }    while (j <= n) {        temp[k++] = arr[j++];       }        for (i = 0; i < k; i++) {        arr[first + i] = temp[i];       }}