快速排序
快速排序的执行流程:
(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];
}
}