[数据结构与算法]《数据结构》排序与选择算法篇 简易笔记

简单排序算法（O(n^2)）

冒泡排序

• 算法原理：
  step1: 比较[0] [1]的 大小，交换位置，此时[0][1]排序完毕
  step2: 比较[0] [1] [2] 的大小，交换位置， 此时 [0][1][2]排序完毕
  …
• C实现：

/* 参数 a[]:待排序数组， l:left,排序起始  r:right 排序末尾 */
void sort(Item a[], int l, int r)
{
	for(int i = l + 1; i <= r; i++)
		for(int j = i; j > l; j--)
			cmpswap(a[j-1], a[j]);
}

插入排序

• 算法原理：i次排序之后， a[0]~a[i-1]部分排序完毕， 之后a[i]再继续插入a[0]~a[i-1]之中，这个主要耗时在元素移动上。
• 步骤解析：
  a[10]: {8,7,4,6,0,9,1,2,3,5};

step1: 取得8 和 7对比，7较小，因此7前面的数字往后移，7填充前面的空缺： a[10]: {7,8,4,6,0,9,1,2,3,5};
step1: 取得4 和 7对比，4较小，因此4前面的数字往后移，4填充前面的空缺： a[10]: {4,7,8,6,0,9,1,2,3,5};
step1: 取得6 和 4对比，4较小，不动，取得6和7对比，6较小，因此6前面的数字往后移，6填充前面的空缺： a[10]: {4,6,7,8,0,9,1,2,3,5};
… 这个就是插入，6插入 4 和7中间， 插入排序需要频繁移动数组顺序，链表适用，数组不太适用。

选择排序

• 算法原理：一样是需要遍历，但是与冒泡排序不同的是，并不每次都做交换，而是先记下最大值/最小值
• 步骤解析：
• a[10]: {8,7,4,6,0,9,1,2,3,5};

step1: for 0~10； 记录最小值为a[4] = 0； 调换a[0] 与 a[4]， 把最小值放左边: a[10] = {0,7,4,6,8,9,1,2,3,5};
step1: for 1~10； 记录最小值为a[6] = 1； 调换a[1] 与 a[6]， 把最小值放左边: a[10] = {0,1,4,6,8,9,7,2,3,5};
step1: for 2~10； 记录最小值为a[7] = 2； 调换a[2] 与 a[7]， 把最小值放左边: a[10] = {0,1,2,6,8,9,7,4,3,5};
…以此类推

快速排序算法(O(nlogn))

随机快速排序

• 其实就是上一篇《图解算法》里面的快速排序。
• 核心思路：依然是递归 + 分治策略， 把无限一分为二，直到size 为0 或者1，就算排序完毕，递归返回。
• 区别在于基准值的选择不同，不用a[0]充当基准值，而是使用random（）产生随机值当作下表，a[random()]基准值。
• 解析

int *qsort(int *Array, int Array_size)
{
	if(Array_size <= 1)
	{
		return Array;
	}
	else
	{
		int left_size = 0;
		int right_size = 0;
		int temp = (int *)malloc(Array_size*sizeof(int))
		for(int i = 1; i < Array_size; i++)
		{
			/**区别就是这里：Array[0] 改为随机下标x**/
			int x = rand()%array_size;
			if(Array[x] > Array[i])
			{
				temp[left_size] = Array[i];
				left_size++;
			}
			else
			{
				temp[Array_size-right_size-1] = Array[i];
				right_size++;
			}
		}
		temp[left_size] = Array[x];
		memcpy(Array, temp, sizeof(int)*Array_size)
		qsort(Array,left_size);
		qsort(Array+left_size+1,right_size);
		return Array;
	}
}

非递归快速排序算法（减少栈空间使用）

• 原理：使用栈模拟递归，把每一个产生的left 和 right组合的小数组的下标值存入栈中
• 一种模拟递归的方式，改进快速排序的最坏结果。

三数取中划分算法（不必要每次都递归到数据只剩下2个，也可以在数组5~25时接入其他排序方式）

• 原理：快速排序，当需要排序的数据达到一定个数时候，转用简单排序。
• 实验效果是数据递归到剩下5~25个时，就不需要继续递归，可以直接简单排序这几个。

三划分快速排序算法（当数据中含有大量的重复数据时）

• 三分指的是：分为大于、小于、等于
• 原理：快速排序，记一下数据相同的个数，递归调用的时候注意计算一下下标。

合并排序算法

基本思想：分治原理，将数组分成大小大致相同的两个子集，对两个子集进行排序，最终将排序好的子集合并为所求的排好序的集合。
（快速排序也是分治原理，将数组分割再分割，区别是快速排序使用基准值，而合并排序是直接把数组一分为二，递归一分为二，最后合并 再合并。）

线性时间排序算法

计数排序算法（线性时间，就是线性时间O(n)）

• 基本思想：对每一个输入元素x，确定输入序列中键值小于x的元素的个数。
  有一个比较典型的例题就是：假设有一条速度极快的数据流，数据为a-z；要求每次截断时都要尽可能快的输出排序好的数据流。

• 解析：声明数组array[26]；

char Array[26];
while(ch = getchar())
{
	switch(ch)
	case 'a': array[0]+=1; break;
	case 'b': array[1]+=1; break;
	case 'c': array[2]+=1; break;
	...
}
//最后直接按array里面的值来判断abcdefg....接收到的次数

桶排序算法（线性时间，就是线性时间O(n)）

• 跟计数排序算法类似。
• 基本思想：设置若干个桶，将键值等于i的元素以链表形式全部装入第i个桶中，然后，按桶的顺序将桶元素再顺序连接起来。

基数排序算法（线性时间，就是线性时间O(n)）

• 跟计数排序算法、桶排序算法 类似。
• 基本思想：将输入数据堪称具有相同长度的正整数，然后从最低位开始，按照从低位到高位的次序，依次对上一轮排序后数据的高一位数值做一次排序，直到最高位后完成排序。
• 解析：(书上算法很精妙，直接摘抄，理解了的话，感觉还是挺好玩的，很妙)

void RadixSort(int a[], int l, int r)
{
	int maxv = 0, pow = 1;
	int *b=(int *)malloc(sizeof(int)* (r+1));
	for(int i = 1; i <=r; i++)
	{
		if(a[i] > maxv
		{
			maxv = a[i];//最大值，用来确定循环次数
		}
	}
	//重点就在于下方排序方式，与计数排序、桶排序类似都用到一个cnt++
	while((maxv / pow) > 0)
	{
		int cnt[RADIX] = {0};  //10进制  RADIX = 10
		for(int i = 1; i <= r; i++)
			cnt[a[i]/pow%RADIX]++;//确定数字为a[i]/pow%RADIX的个数
		
		for(int i = 1; i < RADIX; i++)
			cnt[i] += cnt[i-1];//前缀和
		
		//开始排序
		for(int i =r; i>=1; i --)
			b[--cnt[a[i]/pow%RADIX]] = a[i];//这里排序方式挺妙的
	
		for(int i = l; i <=r;i++)
			a[i] = b[i-1];  //回写

		pow*= RADIX;
	}
	free(b);
}

中位数与第k小元素

平均情况下的线性时间选择算法

• 基本思想：
  在一个已排序好的数组里面，要找到第k小元素，则直接a[k];
  如果是一个非排序好的数组里面，使用快速排序同等思路，取随机值，然后

  • 将数组依据随机值下标a[random()]，划分为左右两个小数组，左边小于a[random()]，右边大于a[random()]。
  • a[random()]，与k做比较，看落在左边数组还是右边数组，还是刚好等于k。

• 参考代码（《数据结构》）

Item reandomselect(Item a[], int l, int r, int k)
{
	if(r<=l) return a[r];
	int i = randomparttition(a, r, l);//产生随机值下标的地方，并且数组在a[i]处简单排序，小于a[i]放a[i]左边，大于a[i]则放a[i]右边
	int j = i - l + 1;
	if(j==k) return a[i];
	if(j > k) return randomselect(a, l, i-1, k);//坐落在左边
	else return randomselect(a, i+1, r, k-j);
}

• 同时，分析上述代码可以了解到，他只需要继续对一半数组查找即可，不关心整个数组，因此可不采取递归的做法，而是直接对半边数组循环处理

Item reandomselect(Item a[], int l, int r, int k)
{
	int i,j;
	while(r>l)
	{
		i = randompartition(a, l, r);
		j=i-l+1;
		if(j==k) return a[i];
		if(j>k) r = i-1;
		else {l = r+1; k -=j;}
	}
	return r<i?a[l]:a[r];
}

最坏情况下的线性时间选择算法

• 暂不理解，后续研究透了再解析