#知识框架 在排序过程中，根据数据元素是否完全在内存中，可将排序算法分为内部排序和外部排序，内部排序，是指在排序期间元素全部存放在内存中的排序，外部排序，是指排序期间元素无法全部同时存放在内存中，必须在排序的过程中根据要求不断在内、外之间移动的排序。内部排序包括插入排序（1直接插入排序2折半插入排序3希尔排序）、交换排序（4冒泡排序5快速排序）、选择排序（6简单选择排序7堆排序）、归并排序（8归并排序）、基数排序（9基数排序）、多路归并排序（10多路归并排序） #排序算法 ##插入排序 所有插入排序的思想都是：待排序表L[1…n],在某次排序过程中前面L[1…i-1]已经排好，L[i]待排序，L[i+1…n]为无序序列

void insert_sort(int a[], int N)
{
	int i, j, tmp;
	for (i = 1; i < N; ++i) {  //从1开始排
		tmp = a[i];
		for (j = i; j > 0 && a[j - 1] > tmp; --j) {  //找到合适位置并挪位
			a[j] = a[j - 1];
		}
		a[j] = tmp;  //把a【i】插入
	}

空间复杂度：O(1)


时间复杂度：O(n^2)

void binary_insert_sort(int a[], int N)
{
	int i,j,low, high, mid,tmp;
	for (i = 1; i < N; ++i)    从1开始排
	{
		low = 0, high = i - 1;
		tmp = a[i];
		while(low<=high)     //找到合适位置
	    {
			mid = (low + high) / 2;
		if (tmp > a[mid])
			low = mid + 1;
		else
			high = mid - 1;
		}
		for (j = i; j >high+1 ; --j)  //找到合适位置了，开始挪位
			a[j] = a[j - 1];
		a[low] = tmp;
	}
}

空间复杂度：O(1)


时间复杂度：O(n^2)

void shell_sort(int a[], int N)
{
	int i, j, increment = N / 2;
	int tmp;
		for (increment=N/2; increment >= 1; increment/=2)  //增量从N/2开始递减
		{
			for (i = increment; i<N; i++)  //从a[increment]开始排到N
			{
				tmp = a[i];
				 for(j=i;j>=increment&&tmp<a[j-increment];j-=increment)
				 {
					 a[j] = a[j - increment];
				 }
				 a[j] = tmp;
			}
	}
}

空间复杂度：O(1)


时间复杂度：O(n^1.3) ##交换排序

void bubble_sort_up(int a[], int N)
{
	int i, j;
	bool flag=false;  //flag为标志位，flag=false表示未排序好
	for (i = 0;(i< N-1)&&(flag=false); i++)
	{
		flag = true;
		for (j = N-1; j >i; j--)
		{
			if (a[j] <a[j -1])  //交换
			{
				swap(&a[j],& a[j -1]);
				flag = false;
			}
		}
			
	}
}

void swap(int * p1, int * p2)
{
	int tmp=*p1;
	*p1 = *p2;
	*p2 = tmp;
}

空间复杂度：O(1)


时间复杂度：O(n^2)

void quick_sort(int a[], int left, int right)
{
	if (right - left + 1 > 3) {   //数组至少有四个元素才快速排序
		int i, j, pivot;
		pivot = median3(a, left, right);  选取枢纽元
		i = left, j = right - 1;
		while (1)
		{
			while (a[++i] < pivot) {};  //确定i
			while (a[--j] > pivot) {};  //确定j
			if (i < j)
				swap(&a[i], &a[j]);
			else
				break;
		}
		swap(&a[i], &a[right - 1]);
		quick_sort(a, left, i - 1);
		quick_sort(a, i + 1, right);
	}
	else
		insert_sort(a + left,right-left+1);
}

int median3(int a[], int left, int right)
{
	int center = (left + right) / 2;
	if (a[left] > a[center])
		swap(&a[left], &a[center]);
	if (a[left] > a[right])
		swap(&a[left], &a[right]);
	if (a[center] > a[right])
		swap(&a[center], &a[right]);
	swap(&a[center], &a[right - 1]);
	return a[right - 1];
}

空间复杂度：O(log_2⁡n)


时间复杂度：最坏O(n^2)

void select_sort(int a[], int N)
{
	int i, j,min;
	for (i=0;i<N;++i)
	{
		min =i;
		for (j = i+1; j < N; ++j)
		{
			if (a[j ] < a[min])
				min = j;
				
		}
		swap(&a[min], &a[i]);
	}
}

空间复杂度：O(1)


时间复杂度：O(n^2)