--------------插入排序-------------

1、插入排序思想

插入排序的核心思想是逐步構(gòu)建有序序列：

將數(shù)組分為 “已排序” 和 “未排序” 兩部分，初始時(shí)已排序部分只包含第一個元素。

每次從未排序部分取出第一個元素，將其向前插入到已排序序列中的正確位置，使得插入后的序列依然保持有序。

重復(fù)這個過程，直到所有元素都被 插入到已排序序列中。

這個過程就像整理撲克牌：你會把每一張新摸到的牌，插入到手中已排好序的牌堆里，最終讓整副牌都有序。

2、示例代碼

// 插入排序（此處為降序，升序?qū)?a[end] < tmp 改為 a[end] > tmp）
void InsertSort(int* a, int n)
{
    // 遍歷未排序元素（從第2個元素開始）
    for (int i = 1; i < n; i++)
    {
        int end = i - 1;  // 已排序部分末尾下標(biāo)
        int tmp = a[i];   // 保存當(dāng)前待插入元素

        // 向前查找合適位置，大于tmp（降序）則后移
        while (end >= 0)
        {
            if (a[end] < tmp)
            {
                a[end + 1] = a[end];  // 元素后移騰位置
                end--;
            }
            else
            {
                break;  // 找到位置，退出循環(huán)
            }
        }
        a[end + 1] = tmp;  // 插入到正確位置
    }
}

3、效率分析

時(shí)間復(fù)雜度：最壞情況下，插入第 1 個待排序元素時(shí)最多比較 1 次，第 2 個元素最多比較 2 次…… 第 n-1 個元素最多比較 n-1 次，總比較次數(shù)為等差數(shù)列求和，因此時(shí)間復(fù)雜度為O(N^2)；但在數(shù)組已有序的情況下，每個元素僅需比較 1 次，時(shí)間復(fù)雜度可優(yōu)化至O(N)。

空間復(fù)雜度：僅定義了常數(shù)級的輔助變量，未額外開辟大規(guī)模空間，因此空間復(fù)雜度為O(1)。

穩(wěn)定性：排序是穩(wěn)定的。因?yàn)樵厥侵饌€向前插入的，當(dāng)遇到相等元素時(shí)不會移動，因此相等元素的相對位置在排序前后保持不變。

--------------希爾排序-------------

1、希爾排序思想

希爾排序的核心思想是分組插入排序，逐步縮小增量：

將整個待排序數(shù)組按照某個 增量（步長）分割成若干個子序列，每個子序列的元素在原數(shù)組中是等間隔的。對每個子序列分別進(jìn)行插入排序，通過這種分組排序，讓數(shù)組整體變得 “基本有序”。

然后，逐步縮小增量（通常取上一次的一半），重復(fù)上述分組和插入排序的操作。當(dāng)增量縮小到 1 時(shí)，整個數(shù)組就變成了一個子序列，此時(shí)再進(jìn)行一次插入排序，數(shù)組就完全有序了。

這個過程就像先把亂序的撲克牌按花色分組整理，再按點(diǎn)數(shù)細(xì)分整理，最后整體微調(diào)：

大增量時(shí)，元素移動的跨度大，能快速把亂序的數(shù)組變得 “大致有序”。

小增量時(shí)，數(shù)組已經(jīng)基本有序，插入排序的效率會非常高。

2、示例代碼

void ShellSort(int* a, int n)
{
	 //gap > 1 預(yù)排序
	 //gap == 1 插入排序
	 int gap = n;
	 while (gap > 1)
	 {
		gap = gap / 3 + 1;

        /*----------------多組并排----------------*/
		//for (int i = 0; i < n - gap; i++)
		//{
		//	int end = i;
	    //  int tmp = a[i + gap];

		//	while (end >= 0)
		//	{
		//		if (tmp < a[end])
		//		{
		//			a[end + gap] = a[end];
		//			end -= gap;
		//		}
		//		else
		//		{
		//			break;
		//		}
		//	}

		//	a[end + gap] = tmp;
		//}

       
		/*-------------一組排完排另一組-------------*/
		for (int j = 0; j < gap; j++)
		{
			for (int i = 0; i < n - gap; i += gap)
			{
				int end = i;
				int tmp = a[i + gap];
				while (end >= 0)
				{
					if (tmp > a[end])
					{
						a[end + gap] = a[end];
						end -= gap;
					}
					else
					{
						break;
					}
				}

				a[end + gap] = tmp;

			}

		}
	 }


}

3、效率分析

時(shí)間復(fù)雜度：

1、外層：外層循環(huán)控制增量gap（公式不同如gap/2、gap/3+1會影響效率）從n逐步縮小至 1，迭代次數(shù)為對數(shù)級別，時(shí)間復(fù)雜度為 O(logN)

2、內(nèi)層：剛開始gap很大，for循環(huán)大致在N這個量級（具體看圖），while循環(huán)插入判斷跳的很快，是常量級別的，所以最開始是時(shí)間復(fù)雜度為O(N)，最后gap很小，按理來說應(yīng)該是N^2，但是由于數(shù)組已經(jīng)無限接近有序，所以按最好的情況算O(N)

因此我們可以大概計(jì)算出來應(yīng)該在N*logN這個量級

這是關(guān)于希爾排序時(shí)間復(fù)雜度不同教材的分析：

空間復(fù)雜度：僅定義了常量級的輔助變量，所以為O(1)

穩(wěn)定性：由于是跳躍調(diào)整，相同值的元素可能在分組插入排序的過程中，被交換到彼此的原始相對位置之前，破壞了穩(wěn)定性，所以希爾排序是不穩(wěn)定排序。

--------------選擇排序-------------

1、選擇排序思想

選擇排序的核心思想是逐步選擇最值，構(gòu)建有序序列：

將數(shù)組分為 “已排序” 和 “未排序” 兩部分，初始時(shí)已排序部分為空。每次從未排序部分中選出最?。ɑ蜃畲螅┑脑?，將其與未排序部分的第一個元素交換位置，該元素就加入到已排序部分的末尾。

重復(fù)這個過程，直到所有元素都被納入已排序部分，整個數(shù)組就完全有序了。

這個過程就像從一堆打亂的撲克牌里，每次挑出最小的一張，放到已整理好的牌堆后面，最終完成整副牌的排序。

2、示例代碼

void SelectSort(int* a, int n)
{
	  /*
      int left = 0;
	  while (left < n)
	  {
		  int min = left;
		  for (int i = left + 1; i < n; i++)
		  {
			  if (a[min] > a[i])
			  {
				  min = i;
			  }

		  }

          swap(&a[min],&a[left]);
          left++;
		 
	  }
	  */

      int left = 0;
      int right = n - 1;
      //left == right就表示只有一個元素了，所以沒有選擇的必要了
	  while (left < right)
	  {
            //必須要初始為left，因?yàn)槭莾?nèi)層循環(huán)從left+1開始比較的
            //如果有一個初始不為left，就會跳過left這個值
			int max = left;
            int min = left;

			for (int i = left + 1; i <= right; i++)
			{
				if (a[max] < a[i])
				{
					max = i;
				}

				if (a[min] > a[i])
				{
					min = i;
				}
			}

            swap(&a[left],&a[min]);
            //修正:max有可能和left重疊
			if (left == max)
			{
				max = min;
			}
			swap(&a[right],&a[max]);
			left++;
			right--;

	  }

}

修正：

3、效率分析

時(shí)間復(fù)雜度：第一趟遍歷 n-1 遍數(shù)組，第二趟遍歷 n-2 遍數(shù)組，第 n-1 遍遍歷1遍數(shù)組，是個等差數(shù)列，所以時(shí)間復(fù)雜度為O(N^2)

空間復(fù)雜度：僅使用常量級別的變量，因此空間復(fù)雜度是O(1)

穩(wěn)定性：由于交換操作可能會破壞相同值元素的相對順序，所以選擇排序是不穩(wěn)定排序

---------------堆排序--------------

1、堆排序思想

堆排序的核心思想是利用堆的特性進(jìn)行排序：

將待排序數(shù)組構(gòu)建成一個大頂堆（或小頂堆），堆頂即為當(dāng)前未排序部分的最大值（或最小值）。每次將堆頂元素與當(dāng)前未排序部分的末尾元素交換，使該最大值（或最小值）歸位到正確的排序位置。交換后，堆的結(jié)構(gòu)會被破壞，需要對剩余的未排序元素重新調(diào)整為大頂堆（或小頂堆）。重復(fù)這個過程，直到整個數(shù)組有序。

這個過程就像從一堆石頭里每次挑出最重的一塊，放到已排好的序列末尾，最終讓所有石頭按重量從大到小排好。

2、示例代碼

//向上調(diào)整算法 - 建大堆
void AdjustUp(int* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] > a[parent])
		{
			swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}


 //向下調(diào)整算法
 void AdjustDown(int* a, int n, int parent)
 {
	 int child = 2 * parent + 1;
	 while (child < n)//等于n時(shí)越界一個位置
	 {
		 if (child + 1 < n && a[child + 1] > a[child])
		 {
			 child++;
		 }

		 if (a[child] > a[parent])
		 {
			 swap(&a[child], &a[parent]);
			 parent = child;
			 child = 2 * parent + 1;
		 }
		 else
		 {
			 break;
		 }
	 }
 }


 //堆排序 
 //N*logN
 void HeapSort(int* a, int n)
 {
	 //向下調(diào)整建堆 -- N
	 for (int i = (n - 2) / 2; i >= 0; i--)
	 {
		 AdjustDown(a,n,i);
	 }
	 //向上調(diào)整建堆 -- N*logN
	 //for (int i = 1; i < n; i++)
	 //{
	 //		AdjustUp(a, i);
	 //}


	 //排序
	 int end = n - 1;
	 while (end > 0)
	 {
		 swap(&a[0], &a[end]);
		 AdjustDown(a, end, 0);
		 end--;
	 }
 }

3、效率分析

時(shí)間復(fù)雜度：

向下調(diào)整建堆的時(shí)間復(fù)雜度為O(N)：向下調(diào)整建堆的時(shí)間復(fù)雜度是 O(N)，而不是 O(NlogN)，核心原因是調(diào)整成本被平攤了。堆的底層節(jié)點(diǎn)數(shù)量最多，占了總節(jié)點(diǎn)數(shù)的一半左右，但它們的調(diào)整深度最小；而堆的上層節(jié)點(diǎn)數(shù)量很少，調(diào)整深度才會達(dá)到 O(logN)。這種 “數(shù)量多的節(jié)點(diǎn)成本低，數(shù)量少的節(jié)點(diǎn)成本高” 的反向分布，把整體的平均調(diào)整成本從 O(logN) 拉低到了 O(1)，最終時(shí)間復(fù)雜度就成了 O(N)。

向上調(diào)整建堆的時(shí)間復(fù)雜度為O(NlogN)，它的調(diào)整邏輯與向下調(diào)整正好相反：上層節(jié)點(diǎn)的調(diào)整深度較淺，但下層節(jié)點(diǎn)的調(diào)整深度很深，而堆的下層恰恰包含了大部分元素。因此，整體來看，大部分節(jié)點(diǎn)都需要進(jìn)行約 logN 次調(diào)整，最終時(shí)間復(fù)雜度為 O(NlogN)。

堆排序的完整過程分為建堆和排序階段兩部分：

建堆階段：使用向下調(diào)整建堆，時(shí)間復(fù)雜度為 O(N)

排序階段：共需進(jìn)行 N−1 次堆頂交換與向下調(diào)整，每次調(diào)整的時(shí)間復(fù)雜度為 O(logN)，因此這一階段的時(shí)間復(fù)雜度為 O(NlogN)

將兩部分時(shí)間復(fù)雜度相加，取主導(dǎo)項(xiàng)，堆排序的整體時(shí)間復(fù)雜度為 O(NlogN)，且該復(fù)雜度不受輸入數(shù)據(jù)分布的影響，最優(yōu)、最壞與平均時(shí)間復(fù)雜度均為 O(NlogN)。

空間復(fù)雜度：僅僅使用了常數(shù)級別的變量，所以空間復(fù)雜度為O(1)

穩(wěn)定性：堆排序是不穩(wěn)定的排序算法。因?yàn)樵诙训恼{(diào)整過程中（無論是向上還是向下調(diào)整），相同值的節(jié)點(diǎn)可能會因?yàn)榻粨Q而改變相對順序，破壞了原有的穩(wěn)定性。

--------------冒泡排序-------------

1、冒泡排序思想

冒泡排序的核心思想是通過相鄰元素的比較與交換，讓較大（較小）的元素逐步 “冒泡” 到數(shù)組的末尾。

將數(shù)組視為一個未排序的整體，從頭部開始，依次比較相鄰的兩個元素。

如果前一個元素大于（小于）后一個元素，就交換它們的位置，使較大（較?。┑脑叵蚝笠苿右晃弧?/p>

每一輪遍歷后，當(dāng)前未排序部分的最大值（最小值）會被 “推” 到末尾，成為已排序部分。

重復(fù)這個過程，直到所有元素都完成排序。

這個過程就像水里的氣泡一樣，較大（較小）的元素會慢慢浮到水面（數(shù)組末尾）。

2、示例代碼

 void BubbleSort(int* a, int n)
 {
     //多少趟
	 for (int i = 0;i < n - 1;i++)
	 {
		 //單趟
		 int flag = 0;
		 for (int j = 1; j < n - i; j++)
		 {
			 if (a[j - 1] > a[j])
			 {
				 swap(&a[j - 1], &a[j]);
				 flag = 1;
			 }
		 }

		 if (flag == 0)
		 {
			 break;
		 }
	  }
 }

3、效率分析

時(shí)間復(fù)雜度：冒泡排序共進(jìn)行 n−1 輪遍歷，總比較次數(shù)為等差數(shù)列求和 2n(n−1)?，時(shí)間復(fù)雜度為 O(N^2)；若加入提前終止優(yōu)化，最優(yōu)情況可降至 O(n)。

空間復(fù)雜度：冒泡排序僅需常數(shù)級別的臨時(shí)變量用于元素交換，因此空間復(fù)雜度為 O(1)。

穩(wěn)定性：冒泡排序是穩(wěn)定的排序算法，因?yàn)樗鼉H在相鄰元素前大于后時(shí)才交換，相同值的元素不會改變相對順序。

上述五大排序性能對比：

希爾排序和堆排序時(shí)間復(fù)雜度都是N*logN這個量級，是這幾個中效率最高的兩個了

（（希爾排序的時(shí)間復(fù)雜度）這是一個簡化說法，嚴(yán)格來說它介于 O(NlogN) 和 O(N2) 之間，取決于增量序列的選擇，但常歸為 O(NlogN) 量級）

接下來就是插入排序和冒泡排序，它倆在數(shù)組有序時(shí)，時(shí)間復(fù)雜度都能達(dá)到 O (N)，最壞都是 O(N^2) 這個量級，但是他們在一些場景下的性能還是有差距的：

有序：一樣

接近有序：有一些差距

部分有序：差距就很大

 這是由于這兩個算法的單次操作導(dǎo)致的：

最后一個就是選擇排序，無論是否有序時(shí)間復(fù)雜度都是在O(N^2)這個量級，也是這幾個中效率最差的排序算法

穩(wěn)定性補(bǔ)充：冒泡、插入排序是穩(wěn)定的；希爾、堆、選擇排序是不穩(wěn)定的。

總結(jié)

到此這篇關(guān)于C語言五大經(jīng)典排序算法插入、希爾、冒泡、選擇、堆排序的文章就介紹到這了,更多相關(guān)C語言算法插入、希爾、冒泡、選擇、堆排序內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論