快速排序

快速排序的执行流程：

(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<j) {

    //在右序列定位一个小于基准值的元素

			j--;

    	}

		while (arr[i] <= temp && i<j) {

//在左序列定位一个大于基准值的元素

			i++;

		}

		if (i < j) { //交换

			t = arr[i];

			arr[i] = arr[j];

			arr[j] = t;

		}

	}

	arr[left] = arr[i];

	arr[i] = temp;

	q_sort(arr,left, i-1); //左侧序列递归

	q_sort(arr,i+1, right); //右侧递归

	return arr;

}

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];

	}

}