六.快速排序

0. 从数列中挑出一个元素，称为 “基准”（pivot）;
1. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
2. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

void quick_sort(int *x, int low, int high)
{
	int i, j, t;
	if (low < high) /*要排序的元素起止下标，保证小的放在左边，大的放在右边。这里以下标为low的元素为基准点*/
	{
		i = low;
		j = high;
		t = *(x+low); /*暂存基准点的数*/
		while (i<j) /*循环扫描*/
		{
			while (i<j && *(x+j)>t) /*在右边的只要比基准点大仍放在右边*/
			{
				j--; /*前移一个位置*/
			}
			if (i<j) 
			{
				*(x+i) = *(x+j); /*上面的循环退出：即出现比基准点小的数，替换基准点的数*/
				i++; /*后移一个位置，并以此为基准点*/
			}
			while (i<j && *(x+i)<=t) /*在左边的只要小于等于基准点仍放在左边*/
			{
				i++; /*后移一个位置*/
			}
			if (i<j)
			{
				*(x+j) = *(x+i); /*上面的循环退出：即出现比基准点大的数，放到右边*/
				j--; /*前移一个位置*/
			}
		}
		*(x+i) = t; /*一遍扫描完后，放到适当位置*/
		quick_sort(x,low,i-1);  /*对基准点左边的数再执行快速排序*/
		quick_sort(x,i+1,high);  /*对基准点右边的数再执行快速排序*/
	}
}

七、堆排序

0. 将待排序序列构建成一个堆 H[0……n-1]，根据（升序降序需求）选择大顶堆或小顶堆；
1. 把堆首（最大值）和堆尾互换；
2. 把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
3. 重复步骤 2，直到堆的尺寸为 1。

void sift(int *x, int n, int s)
{
 int t, k, j;
 t = *(x+s); /*暂存开始元素*/
 k = s;  /*开始元素下标*/
 j = 2*k + 1; /*右子树元素下标*/
 while (j<n)
 {
  if (j<n-1 && *(x+j) < *(x+j+1))/*判断是否满足堆的条件：满足就继续下一轮比较，否则调整。*/
  {
   j++;
  }
  if (t<*(x+j)) /*调整*/
  {
   *(x+k) = *(x+j);
   k = j; /*调整后，开始元素也随之调整*/
   j = 2*k + 1;
  }
  else /*没有需要调整了，已经是个堆了，退出循环。*/
  {
   break;
  }
 ｝
 *(x+k) = t; /*开始元素放到它正确位置*/
}

/*
 功能：堆排序
 输入：数组名称（也就是数组首地址）、数组中元素个数
*/
void heap_sort(int *x, int n)
{
 int i, k, t;
 int *p;
 for (i=n/2-1; i>=0; i--)
 {
  sift(x,n,i); /*初始建堆*/
 } 
 
 for (k=n-1; k>=1; k--)
 {
  t = *(x+0); /*堆顶放到最后*/
  *(x+0) = *(x+k);
  *(x+k) = t;
  sift(x,k,0); /*剩下的数再建堆*/ 
 }
}

八、计数排序

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

九、桶排序

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

0. 在额外空间充足的情况下，尽量增大桶的数量
1. 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要

//注意，这个函数需要输入的数组值在 0 - 99范围内波动
void bucket_sort(int source_array[], int source_array_length)
{
    int i, j, k;
    // 1. 创建100个桶，并初始化为 0。
    int tmp_bucket[100] = {0};
    // 2. 将桶索引视为数组的“元素”，桶索引对应的值就是数组“该元素的个数”。
    for (i = 0; i < source_array_length; i++)
    {
        // 比如， 若原数组是[4, 2, 1, 0]
        // 桶数组初始为 [0, 0, 0, 0, 0],桶的索引对应了原数组的数据区间
        // 当遍历原数组第一个元素4时，则桶数组[4] 加1，桶数组变为 [0, 0, 0, 0, 1]。用映射替代了比较，实现排序。
        tmp_bucket[source_array[i]]++;
    }
    // 遍历桶数组(桶数组长度100)，改变原数组
    j = 0;
    for (i = 0; i < 100; i++)
    {
        for (k = 0; k < tmp_bucket[i]; k++)
        {
            source_array[j] = i;
            j++;
        }
    }
}

十、基数排序

基数排序（radix sort）属于“分配式排序”，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。

1.首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中：

2.接下来将这些桶子中的数值重新串接起来，接着再进行一次分配，这次是根据十位数来分配：

3.接下来将这些桶子中的数值重新串接起来，如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。

//基数排序  pDataArray 无序数组；iDataNum为无序数据个数
void RadixSort(int* pDataArray, int iDataNum)
{
	int *radixArrays[RADIX_10];    //分别为0~9的序列空间
	for (int i = 0; i < 10; i++)
	{
		radixArrays[i] = (int *)malloc(sizeof(int) * (iDataNum + 1));
		radixArrays[i][0] = 0;    //index为0处记录这组数据的个数
	}
	
	for (int pos = 1; pos <= KEYNUM_31; pos++)    //从个位开始到31位
	{
		for (int i = 0; i < iDataNum; i++)    //分配过程
		{
			int num = GetNumInPos(pDataArray[i], pos);
			int index = ++radixArrays[num][0];
			radixArrays[num][index] = pDataArray[i];
		}
        
		for (int i = 0, j =0; i < RADIX_10; i++)    //收集
		{
			for (int k = 1; k <= radixArrays[i][0]; k++)
				pDataArray[j++] = radixArrays[i][k];
			radixArrays[i][0] = 0;    //复位
		}
	}