/*交换排序的基本思想是：两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。 
应用交换排序基本思想的主要排序方法有：冒泡排序和快速排序。*/

/*  冒泡排序
 *   */

#include <stdio.h>

void bubble_sort(int *x, int n)
{
	int i, j, exchange, temp;	//用exchange保存交换标志
	for (i = n - 1; i > 0; i--) {	//冒泡算法最多做n-1趟排序
		exchange = 0;	//本趟排序开始前，交换标志应为假
		for (j = 0; j < i; j++)	//预置k=0,循环扫描后更新
			if (*(x + j) > *(x + j + 1)) {
				temp = *(x + j);
				*(x + j) = *(x + j + 1);
				*(x + j + 1) = temp;
				exchange = 1;	//发生交换，置标志为1
			}
		if (!exchange)	//如果未发生交换，退出
			return;
	}  
}

int main(void)
{
	int i;
	int a[5] = { 5, 3, 2, -5, 1 };
	bubble_sort(a, 5);
	for (i = 0; i < 5; i++)
		printf("%d ", a[i]);
	return 0;
}

#include <stdio.h>

void select_sort(int a[], int n)
{
	int i, j, temp, iMin;
	for (i = 0; i < n - 1; ++i) {
		iMin = i;
		for (j = i + 1; j < n; ++j)
			if (a[j] < a[iMin])
				iMin = j;
		if (iMin != i)
			temp = a[i], a[i] = a[iMin], a[iMin] = temp;
	}
}

static void merge(int array[], int low, int mid, int high)
{
	int i, k;
	int *temp = (int *) malloc((high-low+1) * sizeof(int)); //申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
	int begin1 = low;
	int end1 = mid;
	int begin2 = mid + 1;
	int end2 = high;
 
	for (k = 0; begin1 <= end1 && begin2 <= end2; ++k)  //比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
		if(array[begin1]<=array[begin2])
			temp[k] = array[begin1++];
		else
			temp[k] = array[begin2++];	
	if(begin1 <= end1) //若第一个序列有剩余，直接拷贝出来粘到合并序列尾
		memcpy(temp+k, array+begin1, (end1-begin1+1)*sizeof(int));
	if(begin2 <= end2) //若第二个序列有剩余，直接拷贝出来粘到合并序列尾
		memcpy(temp+k, array+begin2, (end2-begin2+1)*sizeof(int));
        memcpy(array+low, temp, (high-low+1)*sizeof(int));//将排序好的序列拷贝回数组中
	free(temp);
}


void merge_sort(int array[], unsigned int first, unsigned int last)
{
	int mid = 0;
	if(first<last)
	{
		mid = (first+last)/2;
		merge_sort(array, first, mid);
		merge_sort(array, mid+1,last);
		merge(array,first,mid,last);
	}
}

/* 
 * ===  FUNCTION  ======================================================================
 *         Name:  SHELLSORT
 *  Description:  Donald Shell 最初建议步长选择为n/2并且对步长取半直到步长达到1。虽然这样取可以比O(n2)类的算法（插入排序）更好，但这样仍然有减少平均时间和最差时间的余地。 可能希尔排序最重要的地方在于当用较小步长排序后，以前用的较大步长仍然是有序的。比如，如果一个数列以步长5进行了排序然后再以步长3进行排序，那么该数列不仅是以步长3有序，而且是以步长5有序。如果不是这样，那么算法在迭代过程中会打乱以前的顺序，那就不会以如此短的时间完成排序了。
步长序列 	最坏情况下复杂度
n / 2i 	\mathcal{O}(n2)
2k − 1 	\mathcal{O}(n3 / 2)
2i3i 	\mathcal{O}(nlog2n)

已知的最好步长序列由Marcin Ciura设计（1，4，10，23，57，132，301，701，1750，…） 这项研究也表明“比较在希尔排序中是最主要的操作，而不是交换。”用这样步长序列的希尔排序比插入排序和堆排序都要快，甚至在小数组中比快速排序还快，但是在涉及大量数据时希尔排序还是比快速排序慢。

另一个在大数组中表现优异的步长序列是(斐波那契数列除去0和1将剩余的数以黄金分割比的两倍的幂进行运算得到的数列)：（1, 9, 34, 182, 836, 4025, 19001, 90358, 428481, 2034035, 9651787, 45806244, 217378076, 1031612713, …）[2]
 * =====================================================================================
 */
#include 	<stdio.h>
#include	<stdlib.h>

void shellsort(int data[], int n)
{
	int gap, i, j, temp;

	for (gap = n / 2; gap > 0; gap /= 2)
		for (i = gap; i < n; i++)
			for (j = i - gap; j >= 0 && data[j] > data[j + gap];
			     j -= gap) {
				temp = data[j];
				data[j] = data[j + gap];
				data[j + gap] = temp;
			}
}

int main(void)
{
	int a[] = { 53, 325, 456, 24352, 2345, 32, 234, 23, 21, 2, 3, 4325 };
	shellsort(a, 12);
	for (int i = 0; i < 12; i++)
		printf("%d\t", a[i]);
	return EXIT_SUCCESS;
}

#include 	<stdio.h>
#include	<stdlib.h>

void swap(int v[], int i, int j)
{
	int temp = v[i];
	v[i] = v[j];
	v[j] = temp;
}

void qsort1(int v[], int left, int right)
{
	int i, last;
	if (left >= right)
		return;
	swap(v, left, (left + right) / 2);
	last = left;
	for (i = left + 1; i <= right; i++)
		if (v[i] < v[left])
			swap(v, ++last, i);
	swap(v, left, last);
	qsort1(v, left, last - 1);
	qsort1(v, last + 1, right);
}

void InsertSort(char array[], unsigned int n)
{
	int i, j;
	int temp;
	for (i = 1; i < n; i++) {
		temp = array[i];	//store the original sorted array in temp
		for (j = i; j > 0 && temp < array[j - 1]; j--)	//compare the new array with temp(maybe -1?)
		{
			array[j] = array[j - 1];	//all larger elements are moved one pot to the right
			array[j - 1] = temp;
		}
	}
}