【数据结构】 常见的八大排序算法

概述

排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，这里八大排序就是内部排序，指直接插入，希尔，选择，堆排，冒泡，快排，归并，计数。

下面让我们来共同学习这八大排序吧！🤗🤗🤗

什么是外部排序：

外排序是数据量较大,内存放不下,数据放到外部磁盘空间,一般使用归并排序进行外排序

假设内存为512m,给10亿个数据,然后内存每次读取512m的数据,排序完成后返回给磁盘,然后重复这个过程,直到拍完,然后外部的小文件,再经过归并,即可得到一个有序的数据.        

---

目录

概述

 一、插入排序

1、直接插入排序

2、希尔排序 

二、选择排序

1、直接选择排序

2、堆排序

 

 三、交换排序

1、冒泡排序

2、快速排序

2.1 hoare版本

2.2 挖坑法

2.3 前后指针法

2.4 快排非递归版

四、归并排序

1、归并排序递归版

2、递归排序非递归版

五、计数排序 - 非比较排序

六、对排序的分析总结

什么是排序的稳定性： 

排序算法复杂度及稳定性总结：

---

 一、插入排序

1、直接插入排序

基本思想：

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中（我们假设有序），直到所有的记录插入完为止，得到一个新的有序序列。就像是我们玩扑克牌时按顺序大小整理好牌的过程

动图展示 ：

直接插入排序

实现代码： 

void InsertSort(int* arr, int n)
{
        //我们默认序列有序，从一个数据开始，即只有一个数据有序
	for (int i = 0; i = 0) //利用end来进行单趟遍历排序
		{
			//升序
			if (arr[end] > tmp) //若原数据比插入数据大，则后移一位
			{
				arr[end + 1] = arr[end]; 
				end--;  //向前遍历，进行数据排序
			}
			else  //原数据小于插入数据，直接break
			{
				break;
			}
		}
		arr[end + 1] = tmp; 
	}
}

相关分析 ：

对于插入排序：

时间复杂度

• 最坏：逆序  （计算类似等差数列）  --O(N^2)
• 最好：顺序   （数据有序）               ---O(N) 待排序元素集合越接近有序，直接插入排序算法的时间效率越高

  2、希尔排序 

   希尔排序是1959 年由D.L.Shell 提出来的，相对直接插入排序有较大的改进。希尔排序又叫缩小增量排序.。希尔排序是对直接插入排序的优化。

  基本思想： 

  • 希尔排序 = 预排序（分组插入排序） + 直接插入排序（最后一次为整体排序）
  • 我们先选定一个整数gap，间隔为Gap的数据为一组,然后对这组数据进行排序（预排序）,再分组,再排,直到数组被分完.
  • 将Gap减小,继续分组,排序.
  • 最后Gap设为1,此时数据基本有序，即进行直接插入排序,得到有序数组

    动图展示： 

    希尔排序

     代码实现：

    void ShellSort(int* arr, int n)
    {
    	//多组预排,插排
    	int gap = n; 
    	while (gap > 1) //当gap为1时，最后一次为直接插入排序，循环结束
    	{
    		gap = gap / 3 + 1; //除3能保证最后一次分组 gap == 1，即进行直接插入排序
    	
    		for (int i = 0; i =0) //希尔的单趟排序实现
    			{
    				if (arr[end] > tmp)
    				{
    					arr[end + gap] = arr[end];
    					end -= gap;
    				}
    				else
    				{
    					break;
    				}
    			}
    			arr[end + gap] = tmp;
    		}
    	}
    }

     相关分析：

    1. 希尔排序对直接插入排序的优化在于：优化了直接插入排序对逆序数据排序效率很差的缺点。我们将数据进行了一个gap分组，然后进行组预排序，这样下来数据会越来越接近有序，等到最后一次排序的时候，我们无需进行大量的数据遍历，只需遍历个别不满足升序的数据即可。这样希尔排序效率就会比直接插入排序高很多。
    2. 对于希尔排序的时间复杂度：计算是不好计算的，需要进行数学推导，推导出来平均时间复杂度： O(N^1.3—N^2）

    ---

    二、选择排序

    1、直接选择排序

    基本思想：

    每次将数组遍历一遍，在数组[0,n]中选取最小（最大）的数,存放在序列的起始（或者末尾）位置，在[1,n-1]再次遍历选取,交换,缩减,直到全部待排序的数据元素排完

    优化版：每次遍历待排序数据找出最大和最小的数据，分别排列到序列起始和末尾

    动图展示： 

    选择排序

     代码实现：

    void Swap(int* p1, int* p2)
    {
    	int* tmp = *p1;
    	*p1 = *p2;
    	*p2 = *tmp;
    }
    //一般版
    void SelectSort(int* a, int n)
    {
    	int begin = 0, end = n - 1;
    	while (begin= 0; i--)
    	{
    		Adjustdown(a, n, i);
    	}
    	//交换调整
    	for (i = n - 1; i >= 0; i--)
    	{
    		Swap(&a[0], &a[i]);//与当前堆尾数据交换
    		Adjustdown(a, i, 0);//对交换后堆顶数据进行向下调整
    	}
    }

    相关分析：

    • 堆排序使用堆来选数，效率就会高出很多
    • 核心向下调整算法是实现排序的精髓，建堆同样用到

      ---

       三、交换排序

      1、冒泡排序

      基本思想：

       每次遍历待排序数组，对相邻数据进行比较，将值较大的数据向序列尾部移动，值较小的数据向序列前部移动。

      动图展示： 

      冒泡排序

       代码实现：

      void Bubblesort(int* a, int n)
      {
      	for (int i = 0; i  a[j + 1])//如果前一个值大于后一个值,交换. 
      			{
      				swap(&a[j], &a[j + 1]);
      			}
      		}
      	}
      }
      //优化
      void BubbleSort(int* a, int n)
      {
      	for (int j = 0; j  a[i])
      			{
      				Swap(&a[i - 1], &a[i]);
      				exchange = 1;
      			}
      		}
      		// 一趟冒泡过程中，没有发生交换，说明已经有序了，不需要再处理
      		if (exchange == 0)
      		{
      			break;
      		}
      	}
      }

      相关分析：

      我们可以做一个简单的优化，如果我们排序的某一趟每个元素都不用交换，则说明要排序的元素已经有序，那么后面的排序就可以直接跳出循环了。

      2、快速排序

      2.1 hoare版本

      基本思想：

      我们将左边值设为key,然后右边right先走,找小的,比key小停下来,然后左边left走找比key大,然后交换左边右边，继续上述过程，直至left和right相遇，此时的值一定是比key小的值，我们再把key和这个相遇位置的值进行交换，此时key所在的位置，左边的数据一定比key值小，右边的数据一定比key值大，即key放到了合适的位置上。重复此过程进行递归，直至所有的元素都处在合适位置。

      动图展示：

      

      hoare版

       代码实现：

      int HoareSort(int* arr, int left, int right)
      {
      	int key = left; //我们默认key为左边值
      	while (left = arr[key]) //找小
      		{
      			right--;
      		}
      		while (left  
      相关分析：
       
       
       
      Hoare版本的快排需要注意的地方挺多的：
       
       

      • 如果key后面的每个数都比key小或大的话，那left向后面找或right向前面找，会产生越界访问的问题，所以我们选择在if语句的判断部分逻辑与&&保证left小于right，以免产生越界访问的问题。
      •  在if语句的判断部分，找的数据一定得比key小或大的。因为若相等会产生死循环。

        对次的优化： 

        我们可以对key值的选取进行优化，采用三数取中法让我们选取的key数据在序列中的位置尽量靠中间，以提高递归的效率。同时，递归建立的栈帧数量会随着递归深度的增加而增加，为了避免递归深度太深，造成栈溢出的问题。我们采用小区间优化，当递归区间的数据量较小的时候，采用直接插入法进行排序。

        相关代码：

        //三数取中
        int GetMidIndex(int *arr, int begin, int end)
        {
        	int mid = (begin + end) / 2;
        	if (arr[begin] > arr[end])
        	{
        		if (arr[end] > arr[mid])
        		{
        			return end;
        		}
        		else if (arr[begin]  arr[mid])
        		{
        			return mid;
        		}
        		else
        		{
        			return end;
        		}
        	}
        }
        

        //对小区间优化
        void QuickSort(int* arr, int begin, int end)
        {
        	if ((end - begin)  
        2.2 挖坑法
         
        基本思想：
         
        挖坑法对hoare的思想进行了优化。我们设定key数组左边第一个值为坑,右边right找小,找到比key小的值填到坑位，right就成为新的坑位，然后左边left找大,找到后填到坑位上,left此时更新为新的坑位,循环此过程，right接着找小，left找大，交换形成新的坑位，直至left和right相遇。最后把key放到坑里，即类似于hoare版本key应处于的位置。
         
        动图展示：
         
         
        代码实现： 
         
        int QuickSort2(int* arr, int left, int right) //快速排序挖坑法
        {
        	int mid = GetMidIndex(arr, left, right); //三数取中
        	Swap(&arr[left], &arr[mid]);使中间值永远在最左，便于决定谁先走
        	int hole = left; //对key值保存
        	int key = arr[left];//保存坑位下标
        	while (left = key) //右边找小
        		{
        			--right;
        		}
        		arr[hole] = arr[right]; //填坑
        		hole = right;
        		while (left