详解排序几大算法

一、插入排序

基本思想：

直接插入排序是一种简单的插入排序算法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。

步骤：

当插入第n个元素的时候前面的arr[0]到arr[n-1]都已经排序好了，此时我们将arr[n]与前面的相比较，假设我们需要一个升序的数组，那当arr[n]小于所比较的这个数的时候，就跟其交换位置，原来位置上的元素顺序后移。

动图演示：
在这里插入图片描述
代码实现：

void InsertSort(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;
    }
}

直接插入排序的特性：

元素集合越接近有序，直接插入排序算法的时间效率就越高
时间复杂度：O（N^2）
空间复杂度：O(1)

二、希尔排序

基本思想：

先选定一个整数(通常是gap = n/3+1)，把待排序文件所有记录成各组，所有的距离相等的记录在同一组内，并对每一组内的记录进行排序，然后gap = gap/3+1得到下一个整数，再将数组分成各组，进行插入排序，当gap = 1时，将相当于直接插入排序。
所有我们会发现希尔排序是直接插入算法的基础上进行改进而来，但是它的效率要高于直接插入排序。

动图演示：
在这里插入图片描述

希尔排序的特性：

希尔排序是对直接排序的优化
当gap > 1时都时预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了。

代码实现：

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;
		}
	}
}

希尔排序的时间复杂度：O(n^3/2)
希尔排序的空间复杂度：O(1)

三、选择排序

基本思想：
每次从待排序的数据元素中选最小（或者最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

直接选择排序步骤：

在元素集合 array[i]–array[n-1] 中选择关键码最⼤(小)的数据元素
若它不是这组元素中的最后⼀个(第⼀个)元素，则将它与这组元素中的最后⼀个（第⼀个）元素交换
在剩余的 array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余 1 个元素

动图演示：
在这里插入图片描述
代码实现：

void SelectSort(int* a, int n)
{
   int begin = 0, end = n - 1;
   while (begin < end)
   {
      int mini = begin, maxi = begin;
      for (int i = begin; i <= end; i++)
      {
         if (a[i] > a[maxi])
         {
             maxi = i;
         }
         if (a[i] < a[mini])
         {
             mini = i;
         }
      }
      if (begin == maxi)
      {
          maxi = mini;
      }
      swap(&a[mini], &a[begin]);
      swap(&a[maxi], &a[end]);
      ++begin;
      --end;
   }
}

直接选择排序的时间复杂度：O(N^2)
直接选择排序的空间复杂度：O(1)

四、堆排序

堆排序是指利用堆积树这种数据结构所设计的一种排序算法，它是选择排序的一种。
我们需要注意的是排升序要建大堆，排降序建小堆。
点这里在二叉树里面实现了堆排序

五、冒泡排序

动图演示：
在这里插入图片描述
代码实现：

//冒泡排序
void BubbleSort(int* arr, int n)
{
	int end = n;
	while (end)
	{
		int flag = 0;
		for (int i = 1; i < end; ++i)
		{
			if (arr[i - 1] > arr[i])
			{
				int tmp = arr[i];
				arr[i] = arr[i - 1];
				arr[i - 1] = tmp;
				flag = 1;
			}
		}
		if (flag == 0)
		{
			break;
		}
		--end;
	}
}

冒泡排序的时间复杂度：O(N^2)
冒泡排序的空间复杂度：O(1)

六、快速排序

基本思想：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

hoare版本

算法思想：
1.创建左右指针，确定基准值
2.从右向左找出比基准值小的数据，从左往右找出比基准值大的数据，左右指针数据交换，进入下一次循环

步骤：

我们选定一个key（一般是最右边的数，或者最左边的数）接着我们需要定义一个begin和一个end，begin是从左往右走，end是右往左走。在它们走的过程中，当begin遇到比key大的数据的时候停下来，end继续走，指导遇到一个小于key的数时，两者交换数据，最后直到它们相遇，相遇点的数据和key的数据交换。

动图演示：
在这里插入图片描述

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;
	int left = begin;
	int right = end;
	//选左边为key
	int keyi = begin;
	while (begin < end)
	{
		while (a[end] >= a[keyi] && begin < end)
		{
			--end;
		}
		//左边选大
		while (a[begin] <= a[keyi] && begin < end)
		{
			++begin;
		}
		//小的换到右边，大的换到左边
		swap(&a[begin], &a[end]);
	}
	swap(&a[keyi], &a[end]);
	keyi = end;
	QuickSort(a, left, keyi - 1);
	QuickSort(a,keyi + 1,right);
}

挖坑法

基本思路：
创建左右指针，首先从右往左找出比基准值小的数据，后将其放在左边坑中，当前的位置就变为新的坑，然后在从左往右找出比基准值大的数据，找到后将其放进右边坑中，当前位置变为新的坑，当结束循环的时候将最开始储存的分界值放进当前的坑中，返回当前坑的下标。

步骤：

选出一个数据（可以是最左也可以是最右，一般情况下）存放在key变量中，在这个数据位置形成一个坑，紧接着我们定义一个Left和一个Right，Left从左往右走，Right从右往左走。
需要注意的是如果最左边挖坑，则需要Right先走；反之，则Left先走。

动图演示：
在这里插入图片描述
代码实现：

void QuickSort1(int* a, int begin, int end)
{
	if (begin >= end)
	{
	   return;
	}
	int left = begin,right = end;
	int key = a[begin];
	while (begin < end)
	{
		//找小
		while (a[end] >= key && begin < end)
		{
			--end;
		}
		//小的放到左边的坑里
		a[begin] = a[end];
		//找大
		while (a[begin] <= key && begin < end)
		{
			++begin;
		}
		//大的放到右边的坑里
		a[end] = a[begin];
	}
	a[begin] = key;
	int keyi = begin;
	QuickSort1(a, left, keyi - 1);
	QuickSort1(a, keyi + 1, right);
}

lomuto前后指针

基本思路：
创建前后指针从左往右找比基准值小的进行交换，使得小的都排在基准值的左边。

步骤：

选出一个key，起始时prev指针指向序列开头，cur指针指向prev+1的位置。若cur指向的数据小于key，则prev先向后移动一位，然后将prev和cur指针指向的数据交换，cur++；若cur指向的数据大于key，则cur指向直接++。如此进行下去，直到cur到达end位置，此时将key和++prev指针指向的数据交换即可。

在这里插入图片描述
代码实现：

void QuickSort2(int* arr, int begin, int end)
{
	if (begin >= end)
	{
	   return;
	}
	int cur = begin, prev = begin - 1;
	int keyi = end;
	while (cur != keyi)
	{
		if (arr[cur] < arr[keyi] && ++prev != cur)
		{
			swap(&arr[cur], &arr[prev]);
		}
		++cur;
	}
	swap(&arr[++prev],&arr[keyi]);
	keyi = prev;
	QuickSort2(arr, begin, keyi - 1);
	QuickSort2(arr, keyi + 1, end);

}