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

快速排序（递归）

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

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

时间复杂度：最好情况 O(nlogn)，最坏情况 O( $n^{2}$ )，平均情况 O(nlogn)

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

空间复杂度：最好情况 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 data
	while(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 right
		while(low < high && array[low] < middata) low++;
		// left side, if data is bigger than middle data, data change to high index
		array[high] = array[low];
	}
	// the middle data in the correct position
	array[low] = middata;
	// from the position of the middle data, split to two sides
	quicksort(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

归并排序（递归）

从中间位置，将数据拆分成左右两部分。再分别将左右两部分从各自中间位置再拆分成左右两部分。直到左边或右边只有一个元素。
将最多只有一个元素的左右两边，排序合并在一起。
将排好序的左右两边，排序合并在一起。
重复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 side
	int mid = start + ceil((end - start) / 2);
	mergesort(array, start, mid);
	mergesort(array, mid + 1, end);
	// merge the left and right, sort to the new array
	int 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 data
		if(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 data
		else
		{
			tmparr[k] = array[j];
			j++;
		}
	}
	// elements in the new array copy to the original array
	for(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

希尔排序

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

时间复杂度：O( $n^{1.3}$ ) - O( $n^{2}$ )

插入排序的升级。先根据大间隔，按组进行插入排序，再依次减小间隔，按组进行插入排序。
比 $n^{2}$ 快，但比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 data
	while(gap > 0)
	{
		// from gap to the end, each element compare with data before gap steps
		for(int i = gap; i < length; i++)
		{
			// element cycle compare with data before gap steps, until 0 index
			for(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 step
		gap  = 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");
}