👋本篇基于Fire_Cloud_1大佬的超棒博客和菜鳥教程的排序算法教程，并結(jié)合以往筆記，對所涉及到的排序算法進行梳理，主要用于期末復(fù)習😓，重點側(cè)重于算法思想。

成都創(chuàng)新互聯(lián)專注為客戶提供全方位的互聯(lián)網(wǎng)綜合服務(wù)，包含不限于網(wǎng)站設(shè)計、成都網(wǎng)站設(shè)計、武陵網(wǎng)絡(luò)推廣、重慶小程序開發(fā)公司、武陵網(wǎng)絡(luò)營銷、武陵企業(yè)策劃、武陵品牌公關(guān)、搜索引擎seo、人物專訪、企業(yè)宣傳片、企業(yè)代運營等，從售前售中售后，我們都將竭誠為您服務(wù)，您的肯定，是我們大的嘉獎；成都創(chuàng)新互聯(lián)為所有大學生創(chuàng)業(yè)者提供武陵建站搭建服務(wù)，24小時服務(wù)熱線：18982081108，官方網(wǎng)址：www.cdcxhl.com

👋學習目標

• 能清楚給定一個序列在不同排序算法下不同趟后的結(jié)果（明確思路）
• 知道相關(guān)特征（復(fù)雜度、穩(wěn)定性）

---

🚀冒泡排序

👉筆記博客鏈接：實驗2 排序算法

🔔動圖演示

🔔基本思想

每次冒泡依次比較相鄰元素，并將相鄰元素的較大(小)元向右移動，每一次會把大(小)的換至最右，并重復(fù)這一操作。

💯數(shù)據(jù)的順序排好之后，冒泡算法仍然會繼續(xù)進行下一輪的比較，直到size-1次，后面的比較沒有意義的。如何優(yōu)化?

• 設(shè)置標志位judge
• 如果發(fā)生了交換，judge設(shè)置為true；如果沒有交換就設(shè)置為false。
• 這樣當一輪比較結(jié)束后如果judge仍為false即這一輪沒有發(fā)生交換，說明數(shù)據(jù)的順序已經(jīng)排好，沒有必要繼續(xù)進行下去，實現(xiàn)及時終止。

🔔代碼實現(xiàn)

templatevoid bubbleSort(T *array,int n)
{int temp;//交換用臨時變量
    bool judge = true;//標志是否繼續(xù)交換
	for (int i = 0;judge && (i< n-1);i++)
	{//每次遍歷標志位都要先置為false，才能判斷后面的元素是否發(fā)生了交換
		bool judge = false;
	    for(int j = n-1;j >i;j--)
	    {//把array[0:n-1]中大元素移到右邊 
	    	if(array[j]< array[j-1])
			{		temp = array[j];
                array[j] = array[j-1];
                array[j-1] = temp;
                //只要有發(fā)生交換，judge就置為true
			    judge = true;
	     	}
		}	
	}
 }

👉時間復(fù)雜度：O( n 2 n^2 n2)

---

🚀選擇排序

👉筆記博客鏈接：實驗2 排序算法

🔔動圖演示

🔔基本思想

遍歷全部數(shù)組，把最小的往前排（把大的往后排也可以）

• 在長度為N的無序數(shù)組中，第一次遍歷n-1個數(shù)，找到最小的數(shù)值與第一個元素交換

• 第二次遍歷n-2個數(shù)，找到最小的數(shù)值與第二個元素交換；

  …

• 第n-1次遍歷，找到最小的數(shù)值與第n-1個元素交換，排序完成。

💯數(shù)據(jù)的順序排好之后，選擇排序算法仍然會繼續(xù)進行下一輪的選擇，直到n-1次，后面的比較同樣也是沒有意義的，優(yōu)化方法同冒泡排序，實現(xiàn)及時終止。

• 設(shè)置標志位judge
• 如果發(fā)生了最小值(大值)更新，judge設(shè)置為true；如果沒有就設(shè)置為false。
• 這樣當一輪比較結(jié)束后如果judge仍為false即說明數(shù)據(jù)的順序已經(jīng)排好，沒有必要繼續(xù)進行下去，實現(xiàn)及時終止。

🔔代碼實現(xiàn)

templatevoid selectionSort(T *array,int n)
{int temp;
	bool judge = true;
	for(int i = 0;judge && (i< n-1);i++)//終止條件 
	{int Min = i;
		judge = false;
		for(int j = i+1;j< n;j++)
		{	if(array[Min] >array[j]) Min = j;
			else judge = true;
		}
        if(Min != i)
        {   int temp = array[i];
           array[i] = array[Min];
           array[Min] = temp;
       }
	}
}

👉時間復(fù)雜度：O( n 2 n^2 n2)

---

🚀插入排序

👉筆記博客鏈接：實驗2 排序算法

🔔動圖演示

🔔基本思想

把每一個元素依次作為插入元素 ，找到合適的位置插入，維護一個有序列。（就和玩撲克牌理撲克牌順序一個道理）

• 采用升序插入排序，即先把數(shù)組的第一個元素視為已排序元素
• 后將第二個元素拿去插入，若比第一個小，就插到第一個前，反之插到其后
• 再把第三個元素拿去插入，和前兩個元素都比較，找到合適的位置。
• 以此類推。

🔔代碼實現(xiàn)

templatevoid insertSort(T *array,int n) 
{for (int i = 1;i< n;i++)
	{T x = array[i];//把每一個元素依次作為插入元素 
		int j;
		for(j = i-1;j >= 0 && x< array[j];j--)
		{	array[j + 1] = array[j];
		}
		array[j + 1] = x;
	}
}

👉時間復(fù)雜度：O( n 2 n^2 n2)

---

🚀桶排序

👉筆記博客鏈接：第六章：線性表鏈式描述

🔔動圖演示

🔔基本思想

• 分配：將待排序的數(shù)組(鏈表)中每一個數(shù)根據(jù)他們的范圍一一放入對應(yīng)的桶中

• 排序：在每一個桶的內(nèi)部分別對其進行排序(這里的排序考慮那些內(nèi)部排序)

• 收集：從第一個桶開始，將其中的數(shù)據(jù)一一放回原數(shù)組(鏈表)

  第六章筆記有一個鏈表桶排序例子

因為桶的個數(shù)和大小都是我們?nèi)藶樵O(shè)置的。而每個桶又要避免空桶的情況。所以我們在使用桶排序的時候即需要對待排序數(shù)列要求偏均勻，又要要求桶的設(shè)計兼顧效率和空間。

👉有一個范圍設(shè)定參考公式：范圍gap = (max - min + 1)/桶數(shù)

👉在元素分配時：元素值整除(gap + 1)落到對應(yīng)的桶

🔔代碼實現(xiàn)

針對這一組數(shù)據(jù)，gap = 9，以下為該組數(shù)據(jù)的數(shù)組實現(xiàn)

void BucketSort(int* a, int n)
{int bucket[5][5];// 分配五個桶。
	int bucketsize[5];// 每個桶中元素個數(shù)的計數(shù)器。

	// 初始化桶和桶計數(shù)器。
	memset(bucket, 0, sizeof(bucket));
	memset(bucketsize, 0, sizeof(bucketsize));

	// 把數(shù)組a的數(shù)據(jù)按照范圍放入對應(yīng)桶中
	for (int i = 0; i< n; ++i)
	{bucket[a[i] / 10][bucketsize[a[i] / 10]++] = a[i];
	}

	// 分別對每個桶中的數(shù)據(jù)進行排序
	for (int i = 0; i< 5; ++i)
	{//這里用的是快速排序
		QuickSort(bucket[i], 0, bucketsize[i] - 1);
	}

	// 將把每個桶中的數(shù)據(jù)依次放回數(shù)組a中
	int index = 0;
	for (int i = 0; i< 5; ++i)
	{for (int j = 0; j< bucketsize[i]; ++j)
		{	a[index++] = bucket[i][j];
		}
	}
}

👉時間復(fù)雜度：O( n + k n+k n+k)，n是數(shù)據(jù)規(guī)模，k是桶數(shù)

---

🚀基數(shù)排序

👉筆記博客鏈接：第六章：線性表鏈式描述

🔔動圖演示

🔔基本思想

將整數(shù)按某種基數(shù)r切割成不同的數(shù)字，然后對數(shù)字依次進行排序。一般是按基數(shù)10，因此直接按位數(shù)分解。

應(yīng)用舉例

(重點關(guān)注方法，給出鏈表序列能給出第n趟之后的序列)

🔔擴展：用隊列實現(xiàn)

🔑基本思路：

• 每一數(shù)位排序要完成分發(fā)和回收，且要實現(xiàn)先分發(fā)入桶中的數(shù)據(jù)先回收出來，基于隊列后，【分發(fā)數(shù)據(jù)】就是【尾插】，【回收數(shù)據(jù)】就是【頭刪】
• 針對要比較幾次：在分發(fā)數(shù)據(jù)前我們應(yīng)該先去求出這些數(shù)中大的那個數(shù)，然后再求出這個數(shù)的位數(shù)，那它的位數(shù)多少位，那就需要比較多少次

🔑算法圖解:

🔑代碼實現(xiàn)

#include#define RADIX 10		//表示基數(shù)的個數(shù)
queuequ[RADIX];	//定義桶（每個桶均為一個隊列）

//主體代碼
void RadixSort(int* a, int n)		
{//首先求出數(shù)組中的大值
	int max = GetMax(a, n);
	//求出大值的位數(shù)
	int k = GetDigit(max);
	
	//進行k次的數(shù)據(jù)分發(fā)和回收
	for (int i = 0; i< k; ++i)
	{//分發(fā)數(shù)據(jù)
		Distribute(a, n, i);
		//回收數(shù)據(jù)
		Collect(a);
	}
}

//-------------功能補充------------------
//求解數(shù)組中的大值
int GetMax(int* a, int n)
{int max = a[0];
	for (int i = 0; i< n; ++i)
	{if (a[i] >max)
			max = a[i];
	}
	return max;
}

//求解大值的位數(shù)
int GetDigit(int num)
{//num : 10000
	int count = 0;
	while (num >0)
	{count++;
		num /= 10;
	}
	return count;
}

//獲取數(shù)位邏輯
int GetKey(int value, int k)
{int key = 0;
	while(k >= 0)
	{key = value % 10;
		value /= 10;
		k--;
	}
	return key;
}

//分發(fā)數(shù)據(jù)邏輯
void Distribute(int* a, int n, int k)
{for (int i = 0; i< n; ++i)
	{int key = GetKey(a[i], k);
		qu[key].push(a[i]);
	}
}

//回收數(shù)據(jù)邏輯
void Collect(int* a)
{int index = 0;
	for (int i = 0; i< RADIX; ++i)
	{while (!qu[i].empty())
		{	a[index++] = qu[i].front();
			qu[i].pop();
		}
	}
}

👉時間復(fù)雜度：O( n × k n×k n×k)，n是數(shù)據(jù)規(guī)模，k是桶數(shù)

---

🚀堆排序

👉筆記博客鏈接：

• 第十二章：優(yōu)先級隊列，在了解堆排序之前，一定要先學習堆的相關(guān)概念
• 實驗10.1 堆的操作

🔔動圖演示

🔔算法思想

• 將要排序的n個元素初始化為一個大（小）根堆

• 每次從堆中提?。磩h除）元素。

• 即初始化+依次pop

• 初建小根堆操作后，輸出一次top，就pop一下，pop完后又是合規(guī)的小根堆就又把top輸出，這個過程就是如上的依次pop操作從而實現(xiàn)排序，并借助依次輸出top(即根)實現(xiàn)了升序輸出。
  • 如果想讓降序輸出，可以嘗試將每次pop掉的存入棧，存完再出去，依據(jù)后進先出，實現(xiàn)小根堆堆排序降序輸出。

🔑圖解示例

🔔代碼實現(xiàn)

這里貼的就是實驗10.1的代碼

#includeusing namespace std;

//將一個一維數(shù)組的長度從oldLength變成newLength。（后續(xù)push操作會用到） 
templatevoid changeLengthID(T*& array, int oldLength, int newLength)
{T* newarray = new T[newLength];//函數(shù)首先分配一個新的、長度為newLength的數(shù)組   
    int number = (oldLength< newLength) ? oldLength : newLength; //取min {oldLength, newLength} 
    for (int i = 0; i< number; i++)
		newarray[i] = array[i];//然后把原數(shù)組的前min {oldLength, newLength} 個元素復(fù)制到新數(shù)組中
    delete[] array;//釋放原數(shù)組所占用的空間                      
    array = newarray;//將新數(shù)組賦值到舊數(shù)組完成更改 
}

//小根堆定義及實現(xiàn) 
templateclass minHeap
{public:
    	minHeap(int initialCapacity = 10)
		{//構(gòu)造 
    		arrayLength = initialCapacity + 1;
    		heap = new T[arrayLength];
    		heapSize = 0;
		}
    	~minHeap() {delete[] heap; }//析構(gòu) 
    	const T& top()
    	{//返回優(yōu)先級大的元素的引用 
    		return heap[1];
    	}
    	void pop();//刪除
		void push(const T&theElement);//插入
    	void initialize(T*theHeap, int theSize);//初始化 
    	void output(ostream& out) const;//輸出 
	private:
		T* heap;//一個類型為T的一維數(shù)組 
		int arrayLength;//數(shù)組heap的容量 
    	int heapSize;//堆的元素個數(shù)               
};

//小根堆的插入 
templatevoid minHeap::push(const T& theElement)
{//把元素theElement加入堆
    
	//必要時增加數(shù)組長度 
	if (heapSize == arrayLength - 1)
    {//數(shù)組長度加倍 
        changeLengthID(heap, arrayLength, 2 * arrayLength);
        arrayLength *= 2;
    }
    
	//為元素theElement尋找插入位置 
	//小根堆要求老葉子比新葉子小 
    int currentNode = ++heapSize;//currentNode從新葉子向上移動，就從最底下開始 
    while (currentNode != 1 && heap[currentNode / 2] >theElement)
    {//這個時候老葉子比新葉子大，不能把元素放在這 
        heap[currentNode] = heap[currentNode / 2]; //把大的那個元素賦給currentNode，相當于把大的元素往下移 
        currentNode /= 2;//同時把currentNode（一個打算插入theElement的位置）移向雙親，就往上移                    
    }
    //循環(huán)結(jié)束，即找到合適的位置插入 
    heap[currentNode] = theElement;
}

//刪除操作是針對堆頂元素而言的，即把末尾元素移動到堆頂，再自頂向下(重復(fù)構(gòu)建堆的操作)，遞歸調(diào)整。
templatevoid minHeap::pop()
{//刪除堆頂元素
    heap[1].~T(); 
	//刪除最后一個元素，然后重新建堆（這一步相當于把末尾元素拿出來） 
    T lastElement = heap[heapSize--];
	//開始給拿出來的末尾元素找合適的放入位置，從頂開始，自頂向下調(diào)整 
    int currentNode = 1,
        child = 2;//currentNode的孩子    
    while (child<= heapSize)
    {//heap[child]應(yīng)該是currentNode的更大的孩子（就是說它的值太大了，應(yīng)該往后頭放） 
        if (child< heapSize && heap[child] >heap[child + 1])
            child++;
		
		//可以把lastElement放在heap[currentNode]嗎？ 
		//可以 
        if (lastElement<= heap[child])
            break; 
		//不可以（以下操作和上述push相關(guān)操作同理） 
        heap[currentNode] = heap[child];//把孩子child向上移動 
        currentNode = child;//向下移動一層尋找位置          
        child *= 2;
    }
    heap[currentNode] = lastElement;
}

//初始化一個非空小根堆 
templatevoid minHeap::initialize(T* theHeap, int theSize)
{//在數(shù)組theHeap[1:theSize]中建小根堆（參考p304-305) 
    delete[] heap;
    heap = theHeap;
    heapSize = theSize;
	
	//堆化 
    for (int root = heapSize / 2; root >= 1; root--)
    {T rootElement = heap[root];

        int child = 2 * root; 
        while (child<= heapSize)
        {	//heap[child]應(yīng)該是兄弟中的較小者 
            if (child< heapSize && heap[child] >heap[child + 1])
                child++;
                
			//可以把rootElement放在heap[child / 2]嗎? 
			//可以（原理同上 
            if (rootElement<= heap[child])
                break;  
            //不可以 
            heap[child / 2] = heap[child]; 
            child *= 2;                   
        }
        heap[child / 2] = rootElement;
    }
}

int main(void)
{int m, n;
    cin >>n;
    minHeapminheap(n);
    for (int i = 0; i< n; i++) 
	{int num;
        cin >>num;
        minheap.push(num);
    }
    cout<< minheap.top()<< endl;
    cin >>m;
    for (int i = 0; i< m; i++) 
	{int op, num;
        cin >>op;
        if (op == 1)
		{cin >>num;
            minheap.push(num);
            cout<< minheap.top()<< endl;
        }
        if (op == 2) 
		{minheap.pop();
            cout<< minheap.top()<< endl;
        }
        if (op == 3) 
		{int p;
            cin >>p;
            minHeapminheap1(p);
            for (int i = 0; i< p; i++) 
			{int number;
                cin >>number;
                minheap1.push(number);
            }
            for (int i = 0; i< p; i++) 
			{cout<< minheap1.top()<< " ";
                minheap1.pop();
            }
        }
    }
    return 0;
}

👉時間復(fù)雜度：O( n l o g n nlogn nlogn)

---

🚀歸并排序

👉筆記博客鏈接：第十八章：分而冶之

🔔動圖演示

🔔算法思想

• 利用分而治之方法進行排序算法：
• 將n個元素按非遞增順序排列
  • 若n為1，算法終止；
  • 否則
    • 將這一元素集合分割成兩個或更多個子集合
    • 對每一個子集合分別排序
    • 將排好序的子集合歸并為一個集合
• 即 先使每個子序列有序，再使子序列段間有序

🔔代碼實現(xiàn)

templatevoid mergeSort(T a[],int n)
{//使用歸并排序算法對a[0:n-1]進行排序
	T*b = new T[n];
	int segmentSize = 1;//段的大小
    while(segmentSize< n)
    {mergePass(a,b,segmentSize,n);//從a歸并到b 
        segmentSize += segmentSize;
		mergePass(b,a,segmentSize,n);//從b歸并到a 
        segmentSize += segmentSize;
    }
}

templatevoid mergePass(T x[],T y[],int segmentSize,int n)
{int i = 0;
	while(i<= n-2*segmentSize)
    {//歸并兩個大小為segmentSize的相鄰段
        merge(x,y,i,i+segmentSize-1,i+2*segmentSize-1);
        i = i+2*segmentSize;
    }
	//剩下不足2*segmentSize個元素
    if(i+segmentSize< n)
		merge(x,y,i,i+segmentSize-1,n-1);
	else 
        for(int j = i;j<= n-1;j++)
			y[j] = x[j];//把最后一段復(fù)制到y(tǒng)
}

templatevoid merge(T c[],T d[],int startOfFirst,int endOfFirst,
int endOfSecond)
{int first = startOfFirst,//第一段的游標
		second = endOfFirst+1,//第二段的游標
    	result = startOfFirst;//結(jié)果段的游標
	//當兩個被歸并段都未處理完，則不斷進行歸并
    while((first<= endOfFirst) && (second<= endOfSecond))
    {if(c[first]<= c[second]) 
            d[result++] = c[first++];
		else 
            d[result++] = c[second++];
    }
	//考慮余下的部分
	if (first >endOfFirst)
    {//剩下第二段
		for(int q = second;q<= endOfSecond;q++)
			d[result++] = c[q];
    }
	else 
    {for(int q = first;q<= endOfFirst;q++)
            d[result++] = c[q];
    }
}

👉時間復(fù)雜度：O( n l o g n nlogn nlogn)

---

🚀快速排序

👉筆記博客鏈接：第十八章：分而冶之

🔔動圖演示

🔔算法思想

• 從數(shù)列中取出一個數(shù)作為基準數(shù)
• 分區(qū)
  • 將比這個數(shù)大的數(shù)全放到它的右邊
  • 小于或等于它的數(shù)全放到它的左邊
• 再對左右區(qū)間重復(fù)第二步，直到各區(qū)間只有一個數(shù)

🔔代碼實現(xiàn)

void Sort(node *array,int low,int high)//排序
{if(low >high) return;//排好了，不運行了
	int i,j;
	node index;
	node index;
	index = array[low];//定義基準數(shù) 
	i = low;
	j = high;
 	while(i< j)
	{while(i< j && array[j].weight >= index.weight)
  		{	//從右往左找比基準數(shù)小的
   			j--;
		}	
		if(j >i) 
		{	//交換array[i]和array[j]，并把i右移一位 
			array[i++] = array[j];
		}
		while(i< j && array[i].weight< index.weight)
		{	//從左往右找比基準數(shù)大的
			i++;
		}
		if(j >i) 
		{//交換array[i]和array[j]，并把j左移一位
			array[j--] = array[i];
		}
	}
 	array[i] = index;//基準點歸位
 	Sort(array,low,i-1);//遞歸調(diào)用快排比基準點小的元素
 	Sort(array,i+1,high);//遞歸調(diào)用快排比基準點大的元素
}

👉時間復(fù)雜度：O( n l o g n nlogn nlogn)

---

🚀名次排序補充

👉也出現(xiàn)過，所以也放它進來吧，但是它似乎沒有趟的概念😢

👉筆記博客鏈接：實驗2 排序算法

🔔一句話思路

先計算每個元素的具體位置，再將其移動到相應(yīng)位置

🔔代碼實現(xiàn)

templatevoid rankSort(T *array,int n) 
{T *new_array = new T [n];//創(chuàng)建附加數(shù)組 
	int assist[100]; 
	for(int i = 0;i< n;i++)
    {   assist[i] = 0;
    }
    for(int i = 1;i< n;i++)
    {for(int j = 0;j< i;j++)
        {if(array[j]<= array[i])
                assist[i]++;
            else 
                assist[j]++;      
        }
    }
	for (int i = 0;i< n;i++)
	{//利用輔助數(shù)組，按照名次將array[i]暫時貼到新開辟的new_array[]中 
		new_array[assist[i]] = array[i];
	}
	for (int j = 0;j< n;j++)
	{array[j] = new_array[j];//將數(shù)組array重新進行賦值操作
	}	
	delete []new_array;
}

---

🚀比較總結(jié)

• n：數(shù)據(jù)規(guī)模
• k："桶"的個數(shù)
• In-place：占用常數(shù)內(nèi)存，不占用額外內(nèi)存
• Out-place：占用額外內(nèi)存
• 穩(wěn)定性：排序后 2 個相等鍵值的順序和排序之前它們的順序相同

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

本文題目：數(shù)據(jù)結(jié)構(gòu)|各種排序算法梳理|復(fù)習版-創(chuàng)新互聯(lián)
當前網(wǎng)址：http://weahome.cn/article/degosh.html