【算法】（C语言）：快速排序（递归）、归并排序（递归）、希尔排序

快速排序（递归） 

1. 左指针指向第一个数据，右指针指向最后一个数据。取第一个数据作为中间值。
2. 右指针指向的数据 循环与中间值比对，若大于中间值，右指针往左移动一位，若小于中间值，右指针停住。右指针指向的数据放入左指针指向的位置。
3. 左指针指向的数据 循环与中间值比对，若小于中间值，左指针往右移动一位，若大于中间值，左指针停住。左指针指向的数据放入右指针指向的位置。
4. 重复2和3，直到左指针和右指针指向同一个位置pos，则中间值放入该位置pos。
5. 从中间值所在位置pos将数据分成左边和右边两部分。左边数值都比中间值小，右边数值都比中间值大。
6. 重复1-5，直到左边或右边只有一个数据。到此排序完成。

（注：左指针指向的数据始终比中间值小，右指针指向的数据始终比中间值大。）

时间复杂度：最好情况 O(nlogn)，最坏情况 O()，平均情况 O(nlogn)

• 左右指针依次从头或从尾与中间值比对，一轮比对约n次。
• 若每次取的中间值正好是中间位置的数据，每次都是对半拆分，拆分层级logn，则所有数据需约logn轮的比对，总时间 约 O(nlogn)。
• 若已经排好序了，则每次取的中间值都是最小或最大值，则每次都是依次从下一位数据重新开始，类似斜树，最坏时间约  O()。

空间复杂度：最好情况  O(logn)，最坏情况 O(n)。

• 在原位置排序，使用栈作为辅助空间。每次递归，中间值入栈，递归结束，中间值出栈。
• 若最好情况，拆分层级logn，最多logn个中间值在栈中，则即空间使用 O(logn)。
• 若最坏情况，则递归n次，即空间使用约  O(n)。

---

C语言实现：（quicksort.c）

#include <stdio.h>/* function prototype */
void quicksort(int *, int, int);	// quick sort (recursion)
void traverse(int *, int);		// show element one by one/* main function */
int main(void)
{int arr[] = {4,2,6,9,5,1,3};int n = sizeof(arr) / sizeof(int);traverse(arr, n);quicksort(arr, 0, n - 1);printf("[ after quick sort ] ");traverse(arr, n);return 0;
}
/* subfunction */
void quicksort(int *array, int start, int end)		// quick sort (recursion)
{if(start >= end) return ;int low = start, high = end;int middata = array[low];	// the first element as middle datawhile(low < high){// right side, data is bigger than middle data.High index move a step to left  while(low < high && array[high] >= middata) high--;// right side, if data is smaller than middle data, data change to low index  array[low] = array[high];// left side, data is smaller than middle data.Low index move a step to rightwhile(low < high && array[low] < middata) low++;// left side, if data is bigger than middle data, data change to high indexarray[high] = array[low];}// the middle data in the correct positionarray[low] = middata;// from the position of the middle data, split to two sidesquicksort(array, start, low  - 1);quicksort(array, low + 1, end);
}void traverse(int *array, int length)		// show element one by one
{printf("elements(%d): ", length);for(int k = 0; k < length; k++){printf("%d  ", array[k]);}printf("\n");
}

编译链接： gcc -o quicksort quicksort.c

执行可执行文件： ./quicksort

---

---

归并排序（递归）

1. 从中间位置，将数据拆分成左右两部分。再分别将左右两部分从各自中间位置再拆分成左右两部分。直到左边或右边只有一个元素。
2. 将最多只有一个元素的左右两边，排序合并在一起。
3. 将排好序的左右两边，排序合并在一起。
4. 重复3，直到全部排好序。

时间复杂度：最好情况 O(nlogn)，最坏情况 O(nlogn)，平均情况 O(nlogn)

• 每次对半拆分，拆分层级logn，所有数据都需要比对 进行重新排序合并，一轮比对合并约n次，共约logn轮，则总时间约 nlogn，即 O(nlogn)。

空间复杂度：O(n)

• 有多少数据，就需要多少额外的空间存储 已排好序的数据，即 O(n)。

---

C语言实现：（mergesort.c）

#include <stdio.h>
#include <math.h>/* function prototype */
void mergesort(int *, int, int);	// merge sort (recursion)
void traverse(int *, int);		// show element one by one/* main function */
int main(void)
{int arr[] = {4,2,6,9,5,1,3};int n = sizeof(arr) / sizeof(int);traverse(arr, n);mergesort(arr, 0, n - 1);printf("[ after merge sort ] ");traverse(arr, n);return 0;
}
/* subfunction */
void mergesort(int *array, int start, int end)		// merge sort (recursion)
{if(start >= end) return ;// from the middle, split the array to the left side and the right sideint mid = start + ceil((end - start) / 2);mergesort(array, start, mid);mergesort(array, mid + 1, end);// merge the left and right, sort to the new arrayint tmparr[end - start + 1];int i = start, j = mid + 1;for(int k = 0; k <= end - start; k++){// the right side is over or left data < right data, copy the left dataif(j > end || (i <= mid && array[i] < array[j])){tmparr[k] = array[i];i++;}// the left side is over or left data >= right data, copy the right dataelse{tmparr[k] = array[j];j++;}}// elements in the new array copy to the original arrayfor(int i = start, k = 0; i <= end; i++, k++){array[i] = tmparr[k];}
}void traverse(int *array, int length)		// show element one by one
{printf("elements(%d): ", length);for(int k = 0; k < length; k++){printf("%d  ", array[k]);}printf("\n");
}

编译链接： gcc -o mergesort mergesort.c

执行可执行文件： ./mergesort

---

---

希尔排序

1. 取一定间隔（开始一般为数据量的一半），将数据分为多个组，每个组分别排序。
2. 将间隔减半，数据分为多个组，每个组分别排序。
3. 重复2，直到间隔为1，完成最后的排序。

时间复杂度：O() - O()

• 插入排序的升级。先根据大间隔，按组进行插入排序，再依次减小间隔，按组进行插入排序。
• 比快，但比nlogn慢。

空间复杂度：O(1)

• 在原位置排序，只重复使用了用于交换的临时空间，不随数据量的变动而变动，空间使用为常量(1)。

---

C语言实现：（shellsort.c）

#include <stdio.h>
#include <math.h>/* function prototype */
void shellsort(int *, int);			// shell sort
void traverse(int *, int);			// show element one by one/* main function */
int main(void)
{int arr[] = {4,2,6,9,5,1,3};int n = sizeof(arr) / sizeof(int);traverse(arr, n);shellsort(arr, n);printf("[ after shell sort ] ");traverse(arr, n);return 0;
}
/* subfunction */
void shellsort(int *array, int length)		// shell sort
{int gap = ceil(length / 2);	// steps of two comparative datawhile(gap > 0){// from gap to the end, each element compare with data before gap stepsfor(int i = gap; i < length; i++){// element cycle compare with data before gap steps, until 0 indexfor(int j = i; j >= gap; j -= gap){if(array[j] < array[j - gap]){int tmp = array[j];array[j] = array[j - gap];array[j - gap] = tmp;}}}// reduce the stepgap  = ceil(gap / 2);}
}void traverse(int *array, int length)		// show element one by one
{printf("elements(%d): ", length);for(int k = 0; k < length; k++){printf("%d  ", array[k]);}printf("\n");
}

编译链接： gcc -o shellsort shellsort.c

执行可执行文件： ./shellsort