目錄

?一. 前言

二. 排序的概念及運用

? ? ? ? 2.1 排序的概念

? ? ? ? 2.2 排序的運用

? ? ? ? 2.3 常見的排序算法

三.?冒泡and選擇排序

? ? ? ? 3.1 冒泡排序

????????3.2 選擇排序

四. 各大排序算法的復雜度和穩(wěn)定性

?一. 前言

? ? ? ?從本期開始，我們的數(shù)據(jù)結(jié)構(gòu)將迎來一個新的篇章：排序篇，啪嘰啪嘰

? ? ? ?排序是數(shù)據(jù)結(jié)構(gòu)中非常重要的內(nèi)容，在后續(xù)的內(nèi)容中，我們會對各種各樣的排序算法進行剖析和實現(xiàn)，敬請期待哦?

本期要點

• 對排序進行一個整體的認識
• 介紹一下兩種最簡單的排序
• 籠統(tǒng)地介紹一下各大排序算法的復雜度和穩(wěn)定性

二. 排序的概念及運用

? ? ? ? 2.1 排序的概念

? ? ? ? 排序：所謂排序就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。排序算法，就是如何使得記錄按照要求排列的方法。

????????穩(wěn)定性：假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經(jīng)過排序，這些記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。

????????內(nèi)部排序：數(shù)據(jù)元素全部放在內(nèi)存中的排序。

????????外部排序：數(shù)據(jù)元素太多不能同時放在內(nèi)存中，根據(jù)排序過程的要求不能在內(nèi)外存之間移動數(shù)據(jù)的排序。

? ? ? ? 2.2 排序的運用

? ? ? ? 在日常生活中，我們可以找到許多和排序有關的場景。例如我們進入電腦磁盤右鍵就可以看到一個排序方式的選項，這是對我們電腦的磁盤文件進行排序，你可以根據(jù)需求選擇不同排序方式進行排序

? ? ? ? ?又或者，隨便打開一個網(wǎng)購網(wǎng)站/軟件，例如京東，我們可以看到左上角就可以對商品的某一維度進行排序

? ? ? ? ?再或者，世界500強榜單也是經(jīng)過排序后產(chǎn)生的

總之，無論是在計算機的學習上還是現(xiàn)實生活中，排序都是非常重要的主題，其運用十分廣泛，它無處不在

? ? ? ? 2.3 常見的排序算法

? ? ? ? ?排序算法分為比較類排序和非比較類排序，如下圖所示：

三.?冒泡and選擇排序

本期我們先介紹一下我們的兩個老朋友：冒泡排序和選擇排序

? ? ? ? 3.1 冒泡排序

• 思想 : 在一個序列中，每次對序列中的相鄰記錄的鍵值大小進行比較，將較大(升序)或較小(降序)的記錄向后移動。如此循環(huán)，大/小的記錄會慢慢“浮”到序列的后端，整個過程就像是冒泡一樣，顧稱之為冒泡排序。
• 冒泡過程：以下是對某個序列進行冒泡排序的過程

可以看出，對于上面具有5個元素的無序數(shù)組，我們通過4趟的冒泡后就將其變?yōu)橛行驍?shù)組，每一趟冒泡后都可以使最大的數(shù)沉底。

• ?動圖演示：我們可以通過一下動圖感受一下冒泡兩兩比較的過程：

• ?循環(huán)控制：很明顯，我們需要兩層循環(huán)來控制冒泡排序的過程。內(nèi)層循環(huán)控制當前趟的數(shù)據(jù)交換，外層循環(huán)控制冒泡排序的趟數(shù)。
• 外層循環(huán)結(jié)束條件：由于每一趟結(jié)束后都有一個數(shù)冒到序列后端，因此對于N個數(shù)的序列來說，一共需要N-1趟(只剩一個數(shù)不需要冒泡)。

  	for (int i = 0; i < n - 1; i++) //外層循環(huán)，N-1趟
  	{
          ;  
  	}

• 內(nèi)層循環(huán)結(jié)束條件：內(nèi)層循環(huán)用于數(shù)據(jù)的比較。已知N個數(shù)據(jù)共需比較N-1次，由于每一趟結(jié)束后就有數(shù)據(jù)到正確的位置，下一趟需要比較的數(shù)據(jù)個數(shù)就會少1，因此每趟的比較次數(shù)隨著趟數(shù)的增加呈遞減趨勢，初始為N-1次。

  	for (int i = 0; i < n - 1; i++) //外層循環(huán)，N-1趟
  	{
  		for (int j = 0; j < n - 1 - i; j++) //內(nèi)層循環(huán)，次數(shù)隨趟數(shù)增加而遞減，初始為N-1
  		{
              ;
  		}
  	}

• 完整代碼：

  void swap(int* p1, int* p2)
  {
  	int tmp = *p1;
  	*p1 = *p2;
  	*p2 = tmp;
  }
  void BubblingSort(int* a, int n)
  {
  
  	for (int i = 0; i < n - 1; i++) //外層循環(huán)，N-1趟
  	{
  		for (int j = 0; j < n - 1 - i; j++) //內(nèi)層循環(huán)，次數(shù)隨趟數(shù)增加而遞減，初始為N-1
  		{
  			if (a[j] > a[j + 1]) //升序排列，較大的往后移
  			{
  				swap(&a[j], &a[j + 1]); //交換
  			}
  		}
  	}
  }

• 改進優(yōu)化：上面的代碼還存在著改進空間，我們來看下面兩個情景：

對于情境1，我們只需一趟冒泡即可讓數(shù)組有序，而如果按照上面的代碼，我們依舊要進行4趟的冒泡，即有三趟是無效的。

而情境1就更夸張了，數(shù)組已經(jīng)有序，我們卻傻乎乎的做了4趟無效冒泡。無疑是非常浪費時間的。

---

考慮到這些情況，我們提出了優(yōu)化方案：在每趟結(jié)束后判斷一下當前趟是否發(fā)生了元素交換，如果沒有，則說明序列已經(jīng)有序了，及時止損，反之繼續(xù)。優(yōu)化后的代碼如下：

void swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void BubblingSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++) //外層循環(huán)，N-1趟
	{
        int flag=0; //標識每一趟是否發(fā)生交換 0：沒有  1：有
		for (int j = 0; j < n - 1 - i; j++) //內(nèi)層循環(huán)，次數(shù)隨趟數(shù)增加而遞減，初始為N-1
		{
			if (a[j] > a[j + 1]) //升序排列，較大的往后移
			{
				swap(&a[j], &a[j + 1]); //交換
                flag = 1;
			}
		}
        //判斷是否已經(jīng)有序
        if(flag == 0)
        {
            break; //有序則退出循環(huán)
        }
	}
}

• ?時間/空間復雜度：結(jié)合上面的圖片和代碼我們可以看出，總共N-1趟，每趟N-1，N-2...次比較，共比較 (N-1) + (N-2) + (N-3) + (N-4) + (N-5) + ...... + 1次，時間復雜度為；而由于沒有額外的輔助空間，空間復雜度為。
• 穩(wěn)定性分析：由于我們是將較大的或較小的進行交換，當兩個數(shù)相等時并不會進行交換，因而不會改變相同元素的先后次序，所以冒泡排序是穩(wěn)定的排序。

????????3.2 選擇排序

• 思想 :?每一次從待排序的數(shù)據(jù)元素中選出最小(升序)或最大(降序)的一個元素，存放在序列的起始位置，直到全部待排序的數(shù)據(jù)元素排完。
• 選擇過程：以下是對某個序列進行選擇排序的過程：?

??動圖演示：我們一樣通過動圖感受一下選擇排序的過程：?

• ?循環(huán)控制：類似的，我們需要兩層循環(huán)來控制選擇排序的過程。內(nèi)層循環(huán)遍歷序列找出最大/最小值，外層循環(huán)控制選擇的次數(shù)。
• 外層循環(huán)結(jié)束條件：每一次遍歷完都可以選出一個數(shù)換到起始位置，一共N個數(shù)，故要選N-1次(最后一個數(shù)不需要選擇)

      for (int i = 0; i < n-1; i++) //外層循環(huán)，共要選擇n-1次
  	{
          ;
  	}
  

• 內(nèi)層循環(huán)結(jié)束條件：內(nèi)層循環(huán)通過比較進行選數(shù)，一開始N個數(shù)需要比較N-1次，然后每趟結(jié)束后下一次選擇的起始位置就往后移動一位，比較次數(shù)減1

      for (int i = 0; i < n-1; i++) //外層循環(huán)，共選擇n-1次
  	{
  		for (int j = i + 1; j < n; j++) //內(nèi)層循環(huán)，起始位置開始向后進行比較，選最小值
  		{
              ;
  		}
  	}
  

• 完整代碼：

  void swap(int* p1, int* p2)
  {
  	int tmp = *p1;
  	*p1 = *p2;
  	*p2 = tmp;
  }
  void SelectSort(int* a, int n)
  {
  	for (int i = 0; i < n-1; i++) //外層循環(huán)，共選擇n-1次
  	{
  		int mini = i; //記錄最小值的下標，初始為第一個數(shù)下標
  		for (int j = i + 1; j < n; j++) //內(nèi)層循環(huán)，起始位置開始向后進行比較，選最小值
  		{
  			if (a[mini] > a[j]) //比最小值小，交換下標
  			{
  				mini = j;
  			}
  		}
  		swap(&a[mini], &a[i]); //將最小值與起始位置的數(shù)據(jù)互換
  	}
  }

• 時間/空間復雜度：一共選了N-1次，每次選擇需要比較N-1，N-2，N-3...次，加起來和冒泡一樣時間復雜度為；沒有用到輔助空間，空間復雜度為
• 穩(wěn)定性分析：由于是選數(shù)交換，在交換的過程中很可能會打亂相同元素的順序，例如下面這個例子：

? ? ? ? 我們發(fā)現(xiàn)，在第一趟交換中，黑5被交換到了紅5后面，在整個排序結(jié)束后，黑5依然在紅5的后方，與最開始的順序不一致。由此我們可以得出，選擇排序是不穩(wěn)定的排序。

四. 各大排序算法的復雜度和穩(wěn)定性

廢話不多說，直接上表：

排序算法	時間復雜度(最好)	時間復雜度(平均)	時間復雜度(最壞)	空間復雜度	穩(wěn)定性	數(shù)據(jù)敏感度
比較類排序
冒泡排序					穩(wěn)定	強
選擇排序					不穩(wěn)定	弱
直接插入排序					穩(wěn)定	強
希爾排序					不穩(wěn)定	強
堆排序					不穩(wěn)定	弱
快速排序					不穩(wěn)定	強
歸并排序					穩(wěn)定	弱
非比較類排序
基數(shù)排序					穩(wěn)定	弱
桶排序					穩(wěn)定	強
計數(shù)排序					穩(wěn)定	弱

以上，就是本期的全部內(nèi)容啦??

制作不易，能否點個贊再走呢??文章來源地址http://www.zghlxwxcb.cn/news/detail-586064.html

到了這里，關于【數(shù)據(jù)結(jié)構(gòu)】手撕排序NO.1----排序初識的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！