几种常见的排序

排序

  排序：排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作，在生活中排序的运用又很多，如某宝的商品排名，院校排名等。
 
  常见的排序分为：插入排序、选择排序、交换排序、归并排序等，其中插入排序包含直接插入排序与希尔排序，选择排序包含：选择排序、堆排序，交换排序包括：冒泡排序、快速排序，归并排序包含其本身。
 
  本次主要介绍插入排序与选择排序中的堆排序，插入排序的思路比较简单，其基本思想就像平时打扑克牌一样，将无序的牌从大到小或从小到大逐个插入有序的扑克牌中，直到所有的牌有序，更详细的描述如下：当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移。
  其主要代码如下所示：

void InserSort(int* a, int n)
{
    
	
	for (int i = 0;i < n-1;++i)
	{
    
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
    
			if (a[end] > tmp)
			{
    
				a[end + 1] = a[end];
				--end;
			}
			else
			{
    
				break;
			}
		}
		a[end + 1] = tmp;
	}

}

  先理解while里面的内容，相当于单趟插入排序，假设end位置为3，则从数组的第三个数作为开始，从end向数组下标为0的位置逐次靠近，若a[end]>a[end+1]的话，将end位置的数往后挪一个，再将end–，就是逐次靠近数组下标为0的过程，直到前end的个数有序，而for语句的过程相当于控制前n个数有序的过程，这就是直接插入的过程，但是直接插入在时间复杂度上表现为O(N^2)，因为在数组最坏的情况（数组为逆序，此时需要排升序），故针对此情况，希尔提出了一种改进直接插入排序的方法，即希尔排序。
  希尔排序的过程由预排序到直接排序的过程，在预排序的过程中，使用间隔空间排序的方法，使用gap来表示整个间隔的大小，其预排序的思路与直接插入排序一致，不同的是，直接插入排序是将两个相邻的数进行比较，然后将较大者往后挪（在排升序的情况下，降序相反），而预排序的过程是间隔gap的两个数进行比较，较大者往后挪，当gap为1时，其就是直接插入排序，gap值越大，越大的数越快的到达尾端（在升序的情况下），但其越不接近有序，gap越小，其越接近有序，但较大的数越慢到达尾端，下图显示了不同gap值下，数组排序的不同状态。
  希尔排序的代码如下：

void ShellSort(int* a, int n)
{
    
	int gap = n;
	while (gap > 1)
	{
    
		gap = gap / 3 + 1;
		for (int i = 0;i < n - gap;++i)
		{
    
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
    
				if (a[end] > tmp)
				{
    
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
    
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}

}

  希尔排序通过gap来控制预排序的过程，当gap值为1时，排序为直接插入排序，最终完成对数组的排序，希尔排序的时间复杂度在O（n^1.5）左右，其时间复杂度计算较为繁琐，这里就不展开讨论，后续继续分享其他几种排序的思路，并讨论其时间复杂度，与稳定性。