常见的排序算法详解（一）_m0_60502858的博客

排序统一按升序来排数

• 直接插入排序

直接插入排序是一种简单的排序，其思想是将一组待排序的数逐个插到已经有序的一个序列中。对一个数组进行排序，就把第一个位置的数当成已经有序的系列，后面的数依次插到这个有序序列，最后该数组就有序了。

日常生活中我们玩扑克牌就利用了这种思想。

先来完成将一个数插入到序列中这一趟排序的实现。
设有序序列区间是[0,end],即序列最后一个数的下标值用变量end来存储，然后取它左边无序的第一个数用变量x来存储，比较x与end位置的数的大小，如果x小于这个数将这个数往右移动一个位置就再去比较这个数左边的另一个数，直到找到一个比x要小的数，将x插入到这个数的右边，因为事先已经保存了要插入的数据，所以有序序列中的数往后挪动过程中不会因为覆盖右边的数据而造成数据丢失。

int end  ;          //end中存有序序列最右端下标
int x=a[end+1];    //无序的第一个数开始逐个插入有序序列中
while(end>=0)   //   控制一趟插入的边界条件，当与最左边的数比较完后可以确定是插入到该数的左边还是右边
{
  if(a[end]>x)
  {
     a[end+1]=a[end];          //该处不是可以插入的位置就挪动一位
       end--;   //   与下一个数比较看能否插入到它右边
  }
  else
  {
     break;          //已经可以插入的位置就跳出
  }
}
a[end+1]=x;      //当因为end=-1，即比第一个数还小时退出循环，这时x插
                 //入到第一个位置，当因为break推出循环即已经再序列中找到比x小的数了，
                 //要将x插入到该数左边位置。两种情况都时用这行代码实现

单趟完成后，此时x又保存下一个要插入的数，重复单趟插入的步骤插入到有序序列，则直接插入排序的算法可用下面代码实现

void insertsort(int* a, int n)
{
  for (int i = 0; i < n - 1; i++)//数列中一个数时是有序的，将剩余n-1各数逐次插入
  {
  	int end = i;
  	int x = a[end + 1];
  	while (end >= 0)
  	{
  		if (x < a[end])
  		{
  			a[end + 1] = a[end];
  			end--;
  		}
  		else
  			break;
  	}
  	a[end + 1] = x;
  }
}

直接插入排序的空间复杂度和时间复杂度分析

• 空间辅助度容易看出是O（1），因为该过程只额外开辟了end，x变量的空间。
• 时间复杂度来看，分最好的情况和最坏的情况，最好时就是数组本来就有序了，遍历数组每次要插入一个数时都是一次判断就跳出循环，时间复杂度为O（N）。最坏情况时原来的数组是逆序的，我们要排升序。每一个要插入的数都插入到第一的位置，各个插入的数执行的次数依次为 1，2```````N-1 为等差数列，时间复杂度为O（N²）.

希尔排序

希尔排序是在直接插入排序的基础上改进的，非常适合对数据个数大的数据排序。前面已经知道直接插入排序在对已经有序或相对有序的数组排序时更快，这里希尔就是利用了这点来优化的，首先定义一个间距gap来对待排序的数据进行分组。

如图所示，对原始一组数来分组间距为3时，第一组9 5 8 5，第二组1 7 6，第三组2 4 3。针对每一组进行直接插入排序，假定所有组都如此排序了一次后为一趟排序，此时相对原来数据肯定更加有序了。先来实现以上的步骤。

for(int j=0;j<gap;j++)   //外层循环就是控制让所有组都完成插入排序
{
for (int i = j; i < n - gap; i+=gap)   //这里内层循环就是按gap分组后一组数据的插入排序                     // 对比可知gap=1时 希尔排序就是直接插入排序
			{
				int end = i;
				int x = a[end + gap];
				while (end >= 0)
				{
					if (x < a[end])
					{
						a[end + gap] = a[end];
						end -= gap;
					}
					else
						break;
				}
				a[end + gap] = x;
			}
}

这样一趟排序完后已经变得有序了，但还没完全有序，接下来要控制gap的变化，直至gap=1排一趟后才能保证绝对有序。
用如下图的过程来表示希尔排序：

void shellsort(int* a, int n)
{
   int gap=n;
   while(gap>1)  //保证里面gap=1时排一趟就完成最终排序了
   {
      gap/=2;
      for(int j=0;j<gap;j++)  
     {
        for (int i = j; i < n - gap; i+=gap) //这里边界条件n-gap,自己动手画一下图就可以知道，对比插入排序就是n-1  ，gap=1；
			{
				int end = i;
				int x = a[end + gap];
				while (end >= 0)
				{
					if (x < a[end])
					{
						a[end + gap] = a[end];
						end -= gap;
					}
					else
						break;
				}
				a[end + gap] = x;
			}
      }
   }
}

还有一种代码更整洁优化的写法

void shellsort(int* a, int n)
{
	int gap = n;
	while(gap > 1)
	{
		gap=gap/2;   //这里也可以是gap=gap/3+1,
		//for (int j = 0; j < gap; j++)
			for (int i = 0; i < n - gap; i++)   //里面两层循坏变成一层即各组数据可以
			//同时进行插入排序，有gap控制间距，其效果和各组数据依次完成插入排序是一样的
			{
				int end = i;
				int x = a[end + gap];
				while (end >= 0)
				{
					if (x < a[end])
					{
						a[end + gap] = a[end];
						end -= gap;
					}
					else
						break;
				}
				a[end + gap] = x;
			}
	}
	
	
}

希尔排序的空间复杂度和时间复杂度分析

• 空间复杂度也是==O（1）==额外之开辟了gap、end、x等变量的空间。
• 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些书中给出的希尔排序的时间复杂度都不固定：
  

• 选择排序

选择排序思想比较简单，就是遍历一便数组找到最大的数与最右端数交换位置，将数组边界n-1,就是在剩下的n-1个数中重新遍历又选出了次大的数再与新界定的数组最右端的数交换位置，重复以上步骤，不断缩减数组边界，最大数往最右边放，直至有序。

此动图显示不断找最小值往最左端放，跟不断找最大值往右边放同理。

void swap(int* a, int* b)   //交换两数
{
   int tem = *a;
   *a = *b;
   *b = tem;
}
void selectsort(int* a, int n)
{
   int end = n - 1;
   while (end > 0)
   {
   	int max = 0;
   	for (int i = 0; i <= end; i++)
   	{
   		if (a[i] > a[max])
   		{
   			max = i;
   		}
   	}
   	swap(&a[max], &a[end]);
   	end--;
   }
}

还可以遍历一遍数组时同时找出最大值和最小值分别往两边放

void selectsort(int* a, int n)
{
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
		int max = end, mini = begin;
		for (int i = begin; i <= end; i++)
		{
			if (a[i] > a[max])
				max = i;
			if (a[i] < a[mini])
				mini = i;
		}
		swap(&a[end], &a[max]);
		if (mini == end)                  //如果是先把最大值换到右端，则要判断最小值刚好在右端的情况
			mini = max;                    //如果是先把最小值换到左端，则要判断最大值刚好在左端的情况
		swap(&a[begin], &a[mini]);
		begin++;
		end--;
	}
}

选择排序的空间复杂度和时间复杂度分析

• 空间复杂度为O（1）只额外开辟了几个变量的空间。
• 时间复杂度计算次数依次为 N N-1```````1 等差数列求和后最高项次数为2，时间复杂度为O（n²）同时找最大值和最小值时n的次数依然时2只是系数不同，选择排序没有提前break 有序无序时间复杂度都为O（n²）。

堆排序

堆排序是利用了堆这种数据结构来进行排序的，堆的相关学习可以转到堆的概念，结构及应用。
我们知道堆分大小堆，大堆是大的数在堆顶，所以把堆顶数据与数组末尾交换，然后再向下调整堆，再将n-1个数看成一个堆重新进行以上步骤，就可以完成升序排序，需要注意的是排升序要建大堆，降序要排小堆。

像动图显示一样，先再原数组中通过向下调整建大堆，然后不断交换堆顶与无序序列末尾的数，交换一次就调整一次堆。

void adjustdown(int* a, int n, int parent)     //向下调整堆的函数，来建大堆
{
	int child = 2 * parent + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child + 1] > a[child])
			child++;
		if (a[parent] < a[child])
		{
			swap(&a[parent], &a[child]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
			break;
	}
}
void heapsort(int* a, int n)    
{
	for (int parent = n - 2 / 2; parent >= 0; parent--)   //从倒数第二层开始不断向下调整使整个数组在逻辑上是个大堆
		adjustdown(a, n, parent);
	for (int end = n - 1; end > 0; end--)   //这里就开始不断交换，更新堆，来排升序
	{
		swap(&a[0], &a[end]);
		adjustdown(a, end, 0);
	}
}

堆排序的空间复杂度和时间复杂度分析

• 空间辅助度为O（1）只额外开辟了几个变量的空间。
• 时间复杂度上来说，建大堆是O（N）,从堆顶向下调整时，结构是完全二叉数向下调整h-1次是logn, 不断交换后再向下调整，排序时间复杂度是O（N*logN）。