主頁 > 後端開發 > 第一屆排序演算法性能大賽(上萬字激烈解說)

第一屆排序演算法性能大賽(上萬字激烈解說)

2021-10-22 07:56:12 後端開發

寫在前面
最近學到了一些重要的排序，并且取巧地測了一下各種排序演算法在不同的演算法實作、優化以及遞回和非遞回下的運行速度，想著寫篇文章記錄學習成果，同時分享給大家，
本文一共提及了以下幾種常用到的排序，其他排序使用場景較少，便沒有提及，

并且本文的全部代碼實作均為通俗易懂的c語言，希望能夠得到大家的認可和支持，如果覺得本文不錯的話，歡迎三連哦，好了，接下來就是文章本章了，

文章目錄

    • 必備排序常識
    • 第一組參賽選手：插入排序
      • 1.直接插入排序
      • 2.希爾排序
      • 3.性能比拼時刻
    • 第二組參賽選手：選擇排序
      • 1.直接選擇排序
      • 2.堆排序
      • 3.性能比拼時刻
    • 第三組參賽選手：交換排序
      • 1.冒泡排序
      • 2.快速排序(重量級選手)
      • 3.性能比拼時刻
    • 第四組參賽選手：歸并排序
    • 總決賽

必備排序常識

穩定性：在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序演算法是穩定的；否則稱為不穩定的，
內部排序：資料元素全部放在記憶體中的排序，
外部排序：資料元素太多不能同時放在記憶體中，根據排序程序的要求不能在內外存之間移動資料的排序，
時間復雜度：一個排序演算法在執行程序中所耗費的時間量級的度量，
空間復雜度：一個排序演算法在運行程序中臨時占用存盤空間大小的度量，

注意:在使用的時候盡量按照排序方式的英文書寫，便于閱讀，

第一組參賽選手：插入排序

原理：把待排序的資料按照關鍵碼的大小，按照安排徐規則，將當前資料插入到已經排序好的資料中，使其稱為一個新的排序好的資料，直到所有資料插完為止，
實際中我們玩撲克牌時，就用了插入排序的思想，

1.直接插入排序

排序原理：
當插入第i個元素時，前面的i-1個元素已經時有序的，此時用第i個元素的值和前面i-1個元素進行比較，直到找到插入位置，插入即可，原來位置的元素順序后移，
程序展示：

代碼實作：

// 插入排序
void InsertSort(int* a, int n)
{
	for (int tail = 0;tail < n - 1 ;tail++)
	{
		int temp = tail;//記錄有序序列的最后一個元素的下標
		int x = a[tail + 1];
		while (temp >= 0)
		{
			if (a[temp] > x)//說明還有數大于x，繼續把前面陣列的往后移
			{
				a[temp + 1] = a[temp];
				temp--;
			}
			else//如果前面的值小于x，說明不需要往前進行比較了
			{
				break;
			}
		}
		a[temp + 1] = x;//排到所有小于x的數的后面一位
	}
}

特性總結：

  1. 元素集合越接近有序，直接插入排序演算法的時間效率越高，因為當有序的情況下會直接跳出該次回圈
  2. 時間復雜度：O(N) ~ O(N^2)，最好的情況是剛好和演算法的順序一致的情況，只遍歷一遍；最壞的情況為剛好有序的但是和演算法的順序剛好相反，此時時間復雜度為n * (n-1) * ··· *2 * 1為等引數列，按公式計算得為O(N^2)，所以在資料大部分有序的情況下使用插入排序還是不錯的，
  3. 空間復雜度：O(1)，它是一種穩定的排序演算法
  4. 穩定性：穩定

2.希爾排序

排序原理：

希爾排序法(Shell Sort)又稱縮小增量法，希爾排序法的基本思想是：先選定一個整數，把待排序檔案中所有記錄分成個組，所有距離為的記錄分在同一組內，并對每一組內的記錄進行排序，然后，取，重復上述分組和排序的作業，當到達=1時，所有記錄在統一組內排好序，

程序展示：

代碼實作：

// 希爾排序
void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)//外層回圈不斷進行預排序
	{
		gap =gap / 3 + 1;//取排序的間隔，+1是為了確保一定有1，有一才能正確排出正確的順序
		//gap /= 2;//取除2的商也可以，也滿足最后的數有1
		for (int tail = 0;tail < n - gap ;tail ++)//整體思想和插入排序差不多，但是間隔卻不一樣
		{
			int temp = tail;
			int x = a[tail + gap];
			while (temp >= 0)
			{
				if (a[temp] > x)
				{
					a[temp + gap] = a[temp];
					temp -= gap;
				}
				else
				{
					break;
				}
					
			}
			a[temp + gap] = x;
		}
	}
}

特性總結：

  1. 希爾排序是對直接插入排序的優化，
  2. 當gap > 1時都是預排序，目的是讓陣列更接近于有序，不要小看這些預排序，可以讓插入排序的性能有很大的提升，當gap == 1時，陣列已經接近有序的了，這樣就會很快，這樣整體而言，可以達到優化的效果，后面可以進行性能測驗的對比，
  3. 希爾排序的時間復雜度不好計算，需要進行推導，推匯出來平均時間復雜度：O(n*logn)~O(n^2），當間隔gap取得好的條件下可以達到最好情況，最不理想的情況是當gap == 1的時候，也就是直接插入排序，
  4. 穩定性：不穩定，當相同的值被分到不同的組中在進行排序，不同的組中數值大小不確定，此時就不能保證這些數還能保持先后順序，

3.性能比拼時刻

測驗代碼：

利用時間生成的亂數進行的粗劣測驗，看個熱鬧，哈哈，
如果大家使用這段代碼一定要在release版本下進行測驗哦，因為release版本進行了優化，能夠更加客觀地測驗出速度，

void TestOP()
{
	srand(time(0));
	const int N = 100000;//取十萬個隨機值資料進行排序比較
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	int* a3 = (int*)malloc(sizeof(int) * N);
	int* a4 = (int*)malloc(sizeof(int) * N);
	int* a5 = (int*)malloc(sizeof(int) * N);
	int* a6 = (int*)malloc(sizeof(int) * N);
	int* a7 = (int*)malloc(sizeof(int) * N);

	for (int i = 0; i < N; ++i)
	{
		a1[i] = rand();//生成亂數
		//a1[i] = i;//生成有序數
		a2[i] = a1[i];
		a3[i] = a1[i];
		a4[i] = a1[i];
		a5[i] = a1[i];
		a6[i] = a1[i];
		a7[i] = a1[i];
	}

	int begin1 = clock();
	InsertSort(a1, N);
	int end1 = clock();

	int begin2 = clock();
	ShellSort(a2, N);
	int end2 = clock();

	int begin3 = clock();
	SelectSort(a3, N);
	int end3 = clock();

	int begin4 = clock();
	HeapSort(a4, N);
	int end4 = clock();

	int begin5 = clock();
	QuickSortNonR(a5, 0, N - 1);
	QuickSort(a4, 0, N - 1);
	int end5 = clock();

	int begin6 = clock();
	MergeSort(a6, N);
	int end6 = clock();

	int begin7 = clock();
	BubbleSort(a7, N);
	//BubbleSort(a4, N);
	int end7 = clock();

	printf("InsertSort:%d ms\n", end1 - begin1);
	printf("ShellSort:%d ms\n", end2 - begin2);
	printf("SelectSort:%d ms\n", end3 - begin3);
	printf("HeapSort:%d ms\n", end4 - begin4);
	printf("BubbleSort:%d ms\n", end7 - begin7);
	printf("QuickSort:%d ms\n", end5 - begin5);
	printf("MergeSort:%d ms\n", end6 - begin6);

	free(a1);
	free(a2);
	free(a3);
	free(a4);
	free(a5);
	free(a6);
	free(a7);
}

十萬個隨機資料的測驗結果：

可見此時得益于希爾排序優秀的時間復雜度，快了插入排序將近200倍，希爾排序回圈大概進行的次數為：O(n*logn)約等于170萬，
而直接插入排序接近最壞的情況，O(n^2)后的計算結果為100億次，由此可見兩種排序在這種情況下根
本不是一個數量級的，

一百萬個有序資料的測驗結果：

但是在資料大量并且有序的情況下，直接插入排序的時間復雜度接近于O(n)，在一百萬個資料的條件下耗時大大減少，所以如果在資料大量且接近有序的條件下直接插入排序也是不錯的，
雖然希爾排序的本質是插入排序，但是由于需要預排序，耗時肯定會比直接插入排序多，

所以最后勝出的選手是希爾排序

第二組參賽選手：選擇排序

原理：每一次從待排序的資料元素中選出最小（或最大）的一個元素，存放在序列的起始位置，直到全部待排序的資料元素排完 ，

1.直接選擇排序

排序原理：

第一次從待排序的資料元素中選出最小（或最大）的一個元素，存放在序列的起始位置，然后再從剩余的未排序元素中尋找到最小（大）元素，繼續排在已排序元素后，直到未排序元素個數為0，

程序展示：

代碼實作：

void Swap(int* a, int* b)//交換函式
{
	int temp = *a;
	*a = *b;
	*b = temp;
}

//選擇排序，一次只選擇一個數
void SelectSort(int* a, int n)
{
	for (int i = 0;i < n;i++)
	{
		int temp = i;//保存未排序的元素下標
		for (int j = i; j < n;j++)
		{
			if (a[temp] > a[j])//有元素大于中間值
			{
				temp = j;//更新下標
			}
		}
		if (temp != i)//有元素小于小于未排序的頭元素，交換兩者位置
			Swap(a + i, a + temp);
	}
}

// 選擇排序優化版本，一次回圈可以選出最大和最小的值
void SelectSortOp(int* a, int n)
{
	int end = n - 1;//未排序元素尾位置
	for (int slow = 0;slow < end;slow++)
	{
		int min = slow;//保存最小值的下標
		int max = slow;//保存最大值的下標
		for (int fast = slow + 1;fast < end + 1 ;fast++)
		{
			if (a[fast] < a[min])
			{
				min = fast;
			}
			if (a[fast] > a[max])
			{
				max = fast;
			}
		}
		if(min != slow)//有小于的元素,交換兩者的位置
		Swap(&a[min], &a[slow]);
		if (max == slow)//最大值就是未排序元素首元素,前面發生了值交換,更新下標
			max = min;
		Swap(&a[max], &a[end]);
		end--;
	}
}

特性總結：

  1. 直接選擇排序思考非常好理解，但是效率不是很好，實際中很少使用
  2. 時間復雜度：O(n^2)
  3. 空間復雜度：O(1)
  4. 穩定性：不穩定，交換值的同時可能將其他相同值的位置改變了，
    例： 4 9 5 5 8 5 6 9 -> 4 9 5 9 8 5 6 5
    此時就有相同值的位置順序改變了

2.堆排序

排序原理：

堆排序(Heap Sort)是利用堆進行排序的方法，其基本思想為：將待排序列構造成一個大堆(或小堆)，整個序列的最大值(或最小值)就是堆頂的根結點，將根節點的值和堆陣列的末尾元素交換，此時末尾元素就是最大值(或最小值)，然后將剩余的n-1個序列重新構造成一個堆，這樣就會得到n個元素中的次大值(或次小值)，如此反復執行，最終得到一個有序序列，

堆是用陣串列示的完全二叉樹，要學習堆排序，首先要學習堆的向下調整演算法，因為要用堆排序先得建堆，而建堆需要執行多次堆的向下調整演算法，

堆的向下調整演算法（使用前提）：
?若想將其調整為小堆，那么根結點的左右子樹必須都為小堆，
?若想將其調整為大堆，那么根結點的左右子樹必須都為大堆，

向下調整演算法的基本思想（以建大堆為例）：
?1.從根結點處開始，選出左右孩子中值較大的孩子，
?2.讓大的孩子與其父親進行比較，
若大的孩子比父親還大，則該孩子與其父親的位置進行交換，并將原來大的孩子的位置當成父親繼續向下進行調整，直到調整到葉子結點為止，
若大的孩子比父親小，則不需處理了，調整完成，整個樹已經是大堆了，

使用堆的向下調整演算法，最壞的情況下（即一直需要交換結點），需要回圈的次數為：h - 1次（h為樹的高度），而h = log2(n+1)（n為樹的總結點數），所以堆的向下調整演算法的時間復雜度為：O(logn)，
此時需要找出最后一個有葉子結點的父結點，n為結點的總個數，(n - 2) / 2就是滿足條件的下標，并以該結點從下往上依次向下調整，最后就可以建成一個大堆，
在這里插入圖片描述

代碼實作：

void Swap(int* a, int* b)//交換函式
{
	int temp = *a;
	*a = *b;
	*b = temp;
}

//向下調整函式，保證滿足條件左右子樹是小堆或者是大堆
void AdjustDwon(int* a, int n, int root)
{
	int parent = root;
	int child = root * 2 + 1;
	while (child < n)
	{
		if (child + 1<n && a[child + 1] < a[child])//默認是左孩子
		{
			child += 1;//讓下標為數值較大的孩子
		}
		//改變上下兩個if條件控制為大堆或小堆,同時控制升序和降序
		if (a[child] < a[parent])
		{
			Swap(a + parent, a + child);//交換父結點和較大的孩子
			parent = child;
			child = parent * 2 + 1;//更新父子結點,繼續向下調整
		}
		else
		{
			break;
		}
	}
}
// 堆排序
void HeapSort(int* a, int n)
{
	//找到最后一個有葉子結點的父結點，并以該結點從下往上依次向下調整
	for (int i = (n - 2) / 2; i >= 0;--i)//建堆
	{
		AdjustDwon(a, n, i);
	}
	int end = n - 1;
	for (;end > 0;end--)//逐個取出根結點,再次建堆
	{
		Swap(&a[0], &a[end]);
		AdjustDwon(a, end, 0);
	}
}

整個排序程序：

特性總結：

  1. 堆排序使用堆來選數，效率就高了很多，
  2. 時間復雜度：O(n*logn)

前面提到向下建堆的時間復雜度為O(logn)，相乘后的時間度就為O(n*logn)，

  1. 空間復雜度：O(1)
  2. 穩定性：不穩定，因為向下調整的時候可能將相同的值位置順序改變，
    例：

3.性能比拼時刻

十萬個隨機資料的測驗結果：

因為堆排序的時間復雜度為固定的O(n*logn)，而選擇排序的時間復雜度為固定的O(n^2)，所以在演算法上得到大大提升，看圖快了將近1000倍，

十萬個有序資料的測驗結果：

因為兩個排序演算法的時間復雜度是固定的，就算是有序的資料也吳差別，

所以最后勝出的選手是堆排序

第三組參賽選手：交換排序

原理：所謂交換，就是根據序列中兩個記錄鍵值的比較結果來對換這兩個記錄在序列中的位置，交換排序的特點是：將鍵值較大的記錄向序列的尾部移動，鍵值較小的記錄向序列的前部移動，

1.冒泡排序

排序原理：

比較相鄰的元素，如果第一個比第二個大，就交換他們兩個，
每趟從第一對相鄰元素開始，對每一對相鄰元素作同樣的作業，直到最后一對，
針對所有的元素重復以上的步驟，除了已排序過的元素(每趟排序后的最后一個元素)，直到沒有任何一對數字需要比較，

程序展示：

代碼實作：

//冒泡排序
void BubbleSort(int a[], int n)
{
	for (int i = n;i >= 0;i--)//回圈層數
	{
		int flag = 1;//判斷是否有序的標志位
		for (int j = 0 ;j < i - 1;j++)//比較次數
		{
			if (a[j] > a[j + 1])
			{
				Swap(&a[j], &a[j + 1]);
				flag = 0;
			}
		}
		if (flag)//沒發生交換,說明陣列有序,終止回圈
			break;
	}
}

特性總結：

  1. 冒泡排序是一種非常容易理解的排序
  2. 時間復雜度：O(n^2)
  3. 空間復雜度：O(1)
  4. 穩定性：穩定

2.快速排序(重量級選手)

排序原理：

快速排序是Hoare于1962年提出的一種二叉樹結構的交換排序方法，其基本思想為：任取待排序元素序列中的某元素作為基準值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準值，右子序列中所有元素均大于基準值，然后最左右子序列重復該程序，直到所有元素都排列在相應位置上為止，

對于如何按斬訓準值將待排序列分為兩子序列，常見的方式有：
?1. 挖坑法
?2. 前后指標法(Hoare版本)
?3. 快慢指標法

遞回實作：

挖坑法

排序原理：

挖坑法的單趟排序的基本步驟如下：
?1、選出一個資料（一般是最左邊或是最右邊的）存放在key變數中，在該資料位置形成一個坑，
?2、還是定義一個L和一個R，L從左向右走，R從右向左走，（若在最左邊挖坑，則需要R先走；若在最右邊挖坑，則需要L先走，否則會無法正確排出順序），
?3、在走的程序中，若R遇到小于key的數，則將該數拋入坑位，并在此處形成一個坑位，這時L再向后走，若遇到大于key的數，則將其拋入坑位，又形成一個坑位，如此回圈下去，直到最終L和R相遇，這時將key拋入坑位即可，（選取最左邊的作為坑位）

以上就是挖坑法的單趟排序，經過一次單趟排序，最終也使得key左邊的資料全部都小于key，key右邊的資料全部都大于key，但是此時key的左邊和右邊的資料還是亂序的，
然后將key的左序列和右序列再次進行這種單趟排序，如此反復操作下去，直到左右序列只有一個資料，或是左右序列不存在時，便停止操作，最終資料就是有序的，
?
程序展示：

代碼實作：

//快速排序挖坑法
int PartSort1(int* a, int left, int right)
{
	int start = left;
	int end = right;
	//取一個數值,將比他小的數放左邊,比他大的放右邊
	int key = a[start];
	while (start < end)//前后下標還沒相遇時一直回圈
	{
		int pivot = start;//坑位下標
		while (start < end && a[end] >= key)
		{
			end--;
		}
		a[pivot] = a[end];//將右邊比key小的值放在坑位中
		pivot = end;//更新坑位下標
		while (start < end && a[start] <= key)
		{
			start++;
		}
		a[pivot] = a[start];//將左邊比key小\大的值放在坑位中
		pivot = start;//更新坑位下標
	}
	a[start] = key;//把key放在兩下標相遇的地方
	return start;//回傳key的下標
}

//快速排序遞回實作
void QuickSort(int* a,int left, int right)
{
	if (left >= right)//當兩邊相遇或只有一個資料時,就回傳
	{
		return;
	}
	int index = PartSort1(a, left, right);//得到中間數值的位置

	QuickSort(a, left, index - 1);//遞回左邊
	QuickSort(a, index + 1, right);//遞回右邊
}

注意：
此時快速排序有一個較大的缺陷，因為這里默認選擇的是最左邊的值作key，如果該資料有序且是升序，那么key是所有資料中值最小的，那么排序的只有key的右邊值，每次只能排出一個值，此時的時間復雜度為O(n^2)，為了避免這種特殊情況的出現，所以還得寫一個函式取一個適當的值作key，

代碼如下：

int GetMidIndex(int* a, int left, int right)
{
	int mid = (right + left) >> 1;
	if (a[mid] > a[left])
	{
		if (a[left] > a[right])
		{
			return left;
		}
		else if (a[mid] > a[right])
		{
			return right;
		}
		else
		{
			return mid;
		}
	}
	else
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[right] > a[left])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}

// 快速排序挖坑優化版本
int PartSort1(int* a, int left, int right)
{
	int start = left;
	int end = right;
	int mid = GetMidIndex(a, left, right);//三數取中
	Swap(&a[mid], &a[start]);//將該數默認放在最左邊,好分析寫程序
	//取一個數值,將比他小的數放左邊,比他大的放右邊
	int key = a[start];
	while (start < end)//前后下標還沒相遇時一直回圈
	{
		int pivot = start;//坑位下標
		while (start < end && a[end] >= key)
		{
			end--;
		}
		a[pivot] = a[end];//將右邊比key小的值放在坑位中
		pivot = end;//更新坑位下標
		while (start < end && a[start] <= key)
		{
			start++;
		}
		a[pivot] = a[start];//將左邊比key小\大的值放在坑位中
		pivot = start;//更新坑位下標
	}
	a[start] = key;//把key放在兩下標相遇的地方
	return start;//回傳key的下標
}

前后指標法(Hoare版本)

排序原理：

Hoare版本的單趟排序的基本步驟如下：
?1、選出一個key，一般是最左邊或是最右邊的，
?2、定義一個L和一個R，L從左向右走，R從右向左走，（需要注意的是：若選擇最左邊的資料作為key，則需要R先走；若選擇最右邊的資料作為key，則需要L先走），
?3、在走的程序中，若R遇到小于key的數，則停下，L開始走，直到L遇到一個大于key的數時，將L和R的內容交換，R再次開始走，如此進行下去，直到L和R最終相遇，此時將相遇點的內容與key交換即可，（選取最左邊的值作為key）

經過一次單趟排序，最終使得key左邊的資料全部都小于key，key右邊的資料全部都大于key，
然后我們在將key的左序列和右序列再次進行這種單趟排序，如此反復操作下去，直到左右序列只有一個資料，或是左右序列不存在時，便停止操作，因為這種序列可以認為是有序的，

程序展示：

代碼實作：

// 快速排序前后指標法
int PartSort2(int* a, int left, int right)
{
	int start = left;
	int end = right;
	int mid = GetMidIndex(a, left, right);//三數取中
	Swap(&a[mid], &a[start]);//將該數默認放在最左邊,好分析寫程序
	int key = left;
	while (start < end)
	{
		//從右向左找比key小的值,找到后就停下
		while (start < end && a[start] <= a[key])
			start++;
		//從左往右找比key大的值,找到后就停下
		while (start < end && a[end] >= a[key])
			end--;
		//交換兩值
		Swap(&a[start], &a[end]);
	}
	//執行完回圈后,將key和指標相遇的地方交換
	Swap(&a[start], &a[key]);
	return start;//回傳前后指標相遇的地方
}

快慢指標法

排序原理：

前后指標法的單趟排序的基本步驟如下：
?1、選出一個key，一般是最左邊或是最右邊的，
?2、起始時，prev指標指向序列開頭，cur指標指向prev+1，
?3、若cur指向的內容小于key，則prev先向后移動一位，然后交換prev和cur指標指向的內容，然后cur指標++；若cur指向的內容大于key，則cur指標直接++，如此進行下去，直到cur指標越界，此時將key和prev指標指向的內容交換即可，

經過一次單趟排序，最終也能使得key左邊的資料全部都小于key，key右邊的資料全部都大于key，
然后也還是將key的左序列和右序列再次進行這種單趟排序，如此反復操作下去，直到左右序列只有一個資料，或是左右序列不存在時，便停止操作，

程序展示：

代碼實作：

// 快速排序快慢指標法
int PartSort3(int* a, int left, int right)
{
	int mid = GetMidIndex(a, left, right);//三數取中
	Swap(&a[mid], &a[left]);//將該數默認放在最左邊
	int key = left;
	int fast = key + 1;//初始化快指標
	int slow = key;//慢指標
	while (fast <= right)
	{
		//如果有值小于key并且快慢指標不指向同一塊地方就交換值
		if (a[fast] < a[key] && ++slow != fast)
		{
			Swap(&a[slow], &a[fast]);
		}
		fast++;
	}
	Swap(&a[key], &a[slow]);
	return slow;
}

至此快速排序的三種演算法展示完畢

建議大家使用挖坑法和前后指標法，

優化遞回演算法

考慮到遞回實作排序演算法，當遞回深度太深時，會非常消耗堆疊楨，比如讓遞回深度為20層時，遞回呼叫函式次數為2^20 - 1= 1048575,高達一百萬次，
而最后幾層的堆疊楨消耗最為巨大,第20層呼叫函式為2^19 = 524288,第19層為2^18 = 262144，第18層為2^17 = 131072，
所以為了減少堆疊楨的消耗，我們可以使遞回到較深的時候呼叫其他的排序幫助快速排序實作最后的排序，可以大大減少遞回消耗堆疊楨，提升排序速度，

代碼實作：

//遞回優化版本
void QuickSort(int* a,int left, int right)
{
	if (left >= right)//當兩邊相遇或只有一個資料時,就回傳
	{
		return;
	}

	int index = PartSort1(a, left, right);//得到中間數值的位置

	if (index - left > 100)//當每組只剩100個數未排序時
	{
		QuickSort(a, left, index - 1);//遞回左邊
	}
	else
	{
		InsertSort(a + left, index-left);
	}
	if (right - index > 100)
	{
		QuickSort(a, index + 1, right);//遞回右邊
	}
	else
	{
		InsertSort(a + index+ 1, right - index);
	}
}

非遞回實作：

因為在遞回的程序中未排序的資料左右下標會睡著遞回不斷縮小，直到滿足遞回出口，完成對資料的排序，

如果非遞回實作，需要在回圈中保存資料的下標，模擬遞回的實作，

所以選擇用堆疊保存左右下標，在回圈中將資料分成多部分進行排序，當某一部分排好序后再將左右下標出堆疊，直到堆疊里沒有資料，說明此時排序就完成了，

但是c語言庫沒有堆疊，需要自己實作一個堆疊的結構，這里只給大家看一下函式呼叫介面，了解下實作的思想，

// 快速排序 非遞回實作
void QuickSortNonR(int* a, int left, int right)
{
	Stack stack;
	StackInit(&stack);//堆疊初始化
	StackPush(&stack, left);//模擬遞回將左右下標入堆疊
	StackPush(&stack, right);
	while (!StackIsEmpty(&stack))//判斷堆疊是否為空,不為空說明還需要進行排序
	{
		int end = StackTop(&stack);//取堆疊的頭元素
		StackPop(&stack);//出堆疊
		int start = StackTop(&stack);
		StackPop(&stack);

		int index = PartSort1(a, start, end);//得到標志位的下標
		if (index + 1 < end)//判斷是否只剩一個元素
		{
			StackPush(&stack, index + 1);
			StackPush(&stack, end);
		}
		if (start<index - 1)
		{
			StackPush(&stack, start);
			StackPush(&stack, index - 1);
		}
	}
	StackDestory(&stack);//銷毀堆疊
}

特性總結：

  1. 快速排序整體的綜合性能和使用場景都是比較好的，所以才敢叫快速排序
  2. 時間復雜度：O(n*logn)
  1. 空間復雜度：O(logn)
  2. 穩定性：不穩定，當有相等的值時，不好控制，只能往左邊或右邊放，但是前后順序就不確定了，

3.性能比拼時刻

此前排序的三個演算法：挖坑法，前后指標法，快慢指標法的性能是差不多的，在這里是用的挖坑法進行的測驗，

十萬個資料：

冒泡和快排測驗結果：

冒泡排序的時間復雜度為固定的O(n^2)，而且每回圈一次都可能多次呼叫交換函式，導致耗時較長，快速排序的時間復雜度為O(n*logn)，所以在性能上快速排序快得特別多，

在無三數取中下的測驗結果：

可以看出此時在有序的情況下，快速排序的優勢就已經沒有了，時間復雜度為O(n^2)，接下來看有三數取中的性能，

在有三數取中下的測驗結果：

在有三數取中的條件下，快速排序已經超過無序的消耗時間，所以說在有序的情況下三數取中對快速排序的性能還是有很大提升的，

一百萬個資料：

遞回較深時進行優化：
這里的優化結果是，在每組資料還剩100個資料時，用插入排序進行排序，

可以看出優化過后性能還是有所提升，

遞回和非遞回的性能測驗：

遞回和非遞回的性能上沒有什么差別，但是非遞回能夠節約堆疊楨空間，

第四組參賽選手：歸并排序

排序原理：

歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序演算法，該演算法是采用分治法的一個非常典型的應用，將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序，若將兩個有序表合并成一個有序表，稱為二路歸并，

程序展示：

遞回實作：

在排序的程序中，只依靠原陣列進行排序顯然是不現實的，所以說需要申請一塊等大的輔助陣列幫助排序，每次都將排好的一部分值寫回原陣列中，最后一次寫入時陣列就已經排好順序了，

代碼實作：

//歸并排序，遞回實作
void _MergeSort(int* a, int left, int right,int* temp)
{
	//分解
	if (left >= right)//遞回出口,當只剩一個值時回傳
		return;
	int mid = (left + right) >> 1;//取中間值
	_MergeSort(a, left, mid,temp);//左區間遞回分治
	_MergeSort(a, mid + 1, right,temp);//右區間遞回分治

	//合并
	int start1 = left;
	int start2 = mid + 1;
	int i = left;
	//如果有一塊空間排完序就停止
	while (start1<=mid && start2<= right)
	{
		if (a[start1] > a[start2])//將小的值記錄在輔助空間中
		{
			temp[i++] = a[start2++];
		}
		else
		{
			temp[i++] = a[start1++];
		}
	}
	while (start1 <= mid)//將剩下未排序的值保存在輔助陣列中
	{
		temp[i++] = a[start1++];
	}
	while (start2 <= right)
	{
		temp[i++] = a[start2++];
	}
	//將輔助空間中拍好的值放入原陣列中
	for (i = left;i <= right;i++)
	{
		a[i] = temp[i];
	}
}

void MergeSort(int* a, int n)
{
	int* temp = (int*)malloc(sizeof(int) * n);//額外的輔助空間
	_MergeSort(a, 0, n - 1, temp);
	free(temp);
}

非遞回實作：

非遞回實作排序時，就不能依靠遞回幫助實作分治了，這里需要自己設定控制間隔，合理控制回圈，從小到大將其排好順序寫入原陣列，非遞回也是需要額外的空間來幫助排序的，

不過，在非遞回實作演算法時，需要自己考慮邊界控制，例如當gap == 4的時候，按理來說是兩個四個元素的陣列進行排序，但是當元素只有7個或9個的時候，就要對邊界進行控制了，如果是左區間有值，而右半區間不存在，就可以跳過留給后面，當回圈進行到后面的時候就會進行排序；或者右半區間算多了的情況，就要對區間進行修正，

代碼實作：

void MergeSortNonR(int* a, int n)
{
	int* temp = (int*)malloc(sizeof(int) * n);//輔助空間
	int gap = 1;//歸并的間隔控制
	//回圈模擬遞回合并
	while (gap < n)
	{
		for (int i = 0;i < n;i += 2 * gap)
		{
			//左右區間控制
			int start1 = i, end1 = i + gap - 1;
			int start2 = i + gap, end2 = i + 2 * gap - 1;
			int cur = i;
			// 歸并程序中右半區間可能就不存在,就跳過回圈，留給下一次排序
			if (start2 >= n)
			{
				break;
			}
			// 歸并程序中右半區間算多了, 修正一下
			if (end2 >= n)
			{
				end2 = n - 1;
			}
			while (start1 <= end1 && start2 <= end2)
			{
				if (a[start1] > a[start2])
				{
					temp[cur++] = a[start2++];
				}
				else
				{
					temp[cur++] = a[start1++];
				}
			}
			while (start1 <= end1)
			{
				temp[cur++] = a[start1++];
			}
			while (start2 <= end2)
			{
				temp[cur++] = a[start2++];
			}
			//將排好的部分寫入原陣列中
			for (int j = i;j <= end2;j++)
			{
				a[j] = temp[j];
			}
		}
	gap *= 2;
	}
	free(temp);
}

特性總結：

  1. 歸并的缺點在于需要O(n)的空間復雜度，歸并排序的思考更多的是解決在磁盤中的外排序問題，
  2. 時間復雜度：O(n*logn)
  3. 空間復雜度：O(n)
  4. 穩定性：穩定

用歸并排序實作外排序：

首先，我先說明一下什么是內排序，什么是外排序：
?內排序：資料量相對少一些，可以放到記憶體中進行排序，
?外排序：資料量較大，記憶體中放不下，資料只能放到磁盤檔案中，需要排序，

上面介紹的其他排序演算法均是在記憶體中進行的，對于資料量龐大的序列，上面介紹的排序演算法都束手無策，而歸并排序卻能勝任這種海量資料的排序，

假設現在有10億個整數（4GB）存放在檔案A中，需要我們進行排序，而記憶體一次只能提供512MB空間，歸并排序解決該問題的基本思路如下：
?1、每次從檔案A中讀取八分之一，即512MB到記憶體中進行排序（內排序），并將排序結果寫入到一個檔案中，然后再讀取八分之一，重復這個程序，那么最侄訓生成8個各自有序的小檔案（A1~A8），
?2、對生成的8個小檔案進行一一合并，最終8個檔案被合成為4個，然后再一一合并，就變成2個檔案了，最后再進行一次合并，就變成1個有序檔案了，

注意：這里將兩個檔案進行一一合并，并不是先將兩個檔案讀入記憶體然后進行合并，因為記憶體裝不下，這里的一一合并是利用檔案輸入輸出函式，從兩個檔案中各自讀取一個資料，然后進行比較，將較小的資料寫入到一個新檔案中去，然后再讀取，再比較，再寫入，最終將兩個檔案中的資料全部寫入到另一個檔案中去，那么此時這個檔案又是一個有序的檔案了，

或者這樣進行排序：

總決賽

參賽選手總介紹：

最后一輪的選手是

  • 希爾排序
  • 堆排序
  • 快速排序
  • 歸并排序

十萬個資料：

一百萬個資料：

可以看出最后優勝的選手就是快速排序，成功拿下大賽的冠軍，

完結撒花，

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/330310.html

標籤：java

上一篇：Java學習路線總結（思維導圖篇）

下一篇：看完阿里大佬的程式優化筆記，我從床上爬起來，連夜把專案優化個遍

標籤雲
其他(157675) Python(38076) JavaScript(25376) Java(17977) C(15215) 區塊鏈(8255) C＃(7972) AI(7469) 爪哇(7425) MySQL(7132) html(6777) 基礎類(6313) sql(6102) 熊猫(6058) PHP(5869) 数组(5741) R(5409) Linux(5327) 反应(5209) 腳本語言(PerlPython)(5129) 非技術區(4971) Android(4554) 数据框(4311) css(4259) 节点.js(4032) C語言(3288) json(3245) 列表(3129) 扑(3119) C++語言(3117) 安卓(2998) 打字稿(2995) VBA(2789) Java相關(2746) 疑難問題(2699) 细绳(2522) 單片機工控(2479) iOS(2429) ASP.NET(2402) MongoDB(2323) 麻木的(2285) 正则表达式(2254) 字典(2211) 循环(2198) 迅速(2185) 擅长(2169) 镖(2155) 功能(1967) .NET技术(1958) Web開發(1951) python-3.x(1918) HtmlCss(1915) 弹簧靴(1913) C++(1909) xml(1889) PostgreSQL(1872) .NETCore(1853) 谷歌表格(1846) Unity3D(1843) for循环(1842)

熱門瀏覽
  • 【C++】Microsoft C++、C 和匯編程式檔案

    ......

    uj5u.com 2020-09-10 00:57:23 more
  • 例外宣告

    相比于斷言適用于排除邏輯上不可能存在的狀態，例外通常是用于邏輯上可能發生的錯誤。 例外宣告 Item 1：當函式不可能拋出例外或不能接受拋出例外時，使用noexcept 理由 如果不打算拋出例外的話，程式就會認為無法處理這種錯誤，并且應當盡早終止，如此可以有效地阻止例外的傳播與擴散。 示例 //不可 ......

    uj5u.com 2020-09-10 00:57:27 more
  • Codeforces 1400E Clear the Multiset(貪心 + 分治)

    鏈接：https://codeforces.com/problemset/problem/1400/E 來源：Codeforces 思路：給你一個陣列，現在你可以進行兩種操作，操作1：將一段沒有 0 的區間進行減一的操作，操作2：將 i 位置上的元素歸零。最終問：將這個陣列的全部元素歸零后操作的最少 ......

    uj5u.com 2020-09-10 00:57:30 more
  • UVA11610 【Reverse Prime】

    本人看到此題沒有翻譯，就附帶了一個自己的翻譯版本 思考 這一題，它的第一個要求是找出所有 $7$ 位反向質數及其質因數的個數。 我們應該需要質數篩篩選1~$10^{7}$的所有數，這里就不慢慢介紹了。但是，重讀題，我們突然發現反向質數都是 $7$ 位，而將它反過來后的數字卻是 $6$ 位數，這就說明 ......

    uj5u.com 2020-09-10 00:57:36 more
  • 統計區間素數數量

    1 #pragma GCC optimize(2) 2 #include <bits/stdc++.h> 3 using namespace std; 4 bool isprime[1000000010]; 5 vector<int> prime; 6 inline int getlist(int ......

    uj5u.com 2020-09-10 00:57:47 more
  • C/C++編程筆記：C++中的 const 變數詳解，教你正確認識const用法

    1、C中的const 1、區域const變數存放在堆疊區中，會分配記憶體（也就是說可以通過地址間接修改變數的值）。測驗代碼如下： 運行結果： 2、全域const變數存放在只讀資料段（不能通過地址修改，會發生寫入錯誤）， 默認為外部聯編，可以給其他源檔案使用（需要用extern關鍵字修飾） 運行結果： ......

    uj5u.com 2020-09-10 00:58:04 more
  • 【C++犯錯記錄】VS2019 MFC添加資源不懂如何修改資源宏ID

    1. 首先在資源視圖中，添加資源 2. 點擊新添加的資源，復制自動生成的ID 3. 在解決方案資源管理器中找到Resource.h檔案，編輯，使用整個專案搜索和替換的方式快速替換 宏宣告 4. Ctrl+Shift+F 全域搜索，點擊查找全部，然后逐個替換 5. 為什么使用搜索替換而不使用屬性視窗直 ......

    uj5u.com 2020-09-10 00:59:11 more
  • 【C++犯錯記錄】VS2019 MFC不懂的批量添加資源

    1. 打開資源頭檔案Resource.h，在其中預先定義好宏 ID（不清楚其實ID值應該設定多少，可以先新建一個相同的資源項，再在這個資源的ID值的基礎上遞增即可） 2. 在資源視圖中選中專案資源，按F7編輯資源檔案，按 ID 型別 相對路徑的形式添加 資源。（別忘了先把檔案拷貝到專案中的res檔案 ......

    uj5u.com 2020-09-10 01:00:19 more
  • C/C++編程筆記：關于C++的參考型別，專供新手入門使用

    今天要講的是C++中我最喜歡的一個用法——參考，也叫別名。 參考就是給一個變數名取一個變數名，方便我們間接地使用這個變數。我們可以給一個變數創建N個參考，這N + 1個變數共享了同一塊記憶體區域。(參考型別的變數會占用記憶體空間，占用的記憶體空間的大小和指標型別的大小是相同的。雖然參考是一個物件的別名，但 ......

    uj5u.com 2020-09-10 01:00:22 more
  • 【C/C++編程筆記】從頭開始學習C ++：初學者完整指南

    眾所周知，C ++的學習曲線陡峭，但是花時間學習這種語言將為您的職業帶來奇跡，并使您與其他開發人員區分開。您會更輕松地學習新語言，形成真正的解決問題的技能，并在編程的基礎上打下堅實的基礎。 C ++將幫助您養成良好的編程習慣（即清晰一致的編碼風格，在撰寫代碼時注釋代碼，并限制類內部的可見性），并且由 ......

    uj5u.com 2020-09-10 01:00:41 more
最新发布
  • Rust中的智能指標:Box<T> Rc<T> Arc<T> Cell<T> RefCell<T> Weak

    Rust中的智能指標是什么 智能指標（smart pointers）是一類資料結構，是擁有資料所有權和額外功能的指標。是指標的進一步發展 指標（pointer）是一個包含記憶體地址的變數的通用概念。這個地址參考，或 ” 指向”（points at）一些其 他資料 。參考以 & 符號為標志并借用了他們所 ......

    uj5u.com 2023-04-20 07:24:10 more
  • Java的值傳遞和參考傳遞

    值傳遞不會改變本身，參考傳遞（如果傳遞的值需要實體化到堆里）如果發生修改了會改變本身。 1.基本資料型別都是值傳遞 package com.example.basic; public class Test { public static void main(String[] args) { int ......

    uj5u.com 2023-04-20 07:24:04 more
  • [2]SpinalHDL教程——Scala簡單入門

    第一個 Scala 程式 shell里面輸入 $ scala scala> 1 + 1 res0: Int = 2 scala> println("Hello World!") Hello World! 檔案形式 object HelloWorld { /* 這是我的第一個 Scala 程式 * 以 ......

    uj5u.com 2023-04-20 07:23:58 more
  • 理解函式指標和回呼函式

    理解 函式指標 指向函式的指標。比如： 理解函式指標的偽代碼 void (*p)(int type, char *data); // 定義一個函式指標p void func(int type, char *data); // 宣告一個函式func p = func; // 將指標p指向函式func ......

    uj5u.com 2023-04-20 07:23:52 more
  • Django筆記二十五之資料庫函式之日期函式

    本文首發于公眾號：Hunter后端 原文鏈接：Django筆記二十五之資料庫函式之日期函式 日期函式主要介紹兩個大類，Extract() 和 Trunc() Extract() 函式作用是提取日期，比如我們可以提取一個日期欄位的年份，月份，日等資料 Trunc() 的作用則是截取，比如 2022-0 ......

    uj5u.com 2023-04-20 07:23:45 more
  • 一天吃透JVM面試八股文

    什么是JVM？ JVM，全稱Java Virtual Machine（Java虛擬機），是通過在實際的計算機上仿真模擬各種計算機功能來實作的。由一套位元組碼指令集、一組暫存器、一個堆疊、一個垃圾回收堆和一個存盤方法域等組成。JVM屏蔽了與作業系統平臺相關的資訊，使得Java程式只需要生成在Java虛擬機 ......

    uj5u.com 2023-04-20 07:23:31 more
  • 使用Java接入小程式訂閱訊息！

    更新完微信服務號的模板訊息之后，我又趕緊把微信小程式的訂閱訊息給實作了！之前我一直以為微信小程式也是要企業才能申請，沒想到小程式個人就能申請。 訊息推送平臺🔥推送下發【郵件】【短信】【微信服務號】【微信小程式】【企業微信】【釘釘】等訊息型別。 https://gitee.com/zhongfuch ......

    uj5u.com 2023-04-20 07:22:59 more
  • java -- 緩沖流、轉換流、序列化流

    緩沖流 緩沖流, 也叫高效流, 按照資料型別分類： 位元組緩沖流：BufferedInputStream，BufferedOutputStream 字符緩沖流：BufferedReader，BufferedWriter 緩沖流的基本原理，是在創建流物件時，會創建一個內置的默認大小的緩沖區陣列，通過緩沖 ......

    uj5u.com 2023-04-20 07:22:49 more
  • Java-SpringBoot-Range請求頭設定實作視頻分段傳輸

    老實說，人太懶了，現在基本都不喜歡寫筆記了，但是網上有關Range請求頭的文章都太水了 下面是抄的一段StackOverflow的代碼...自己大修改過的，寫的注釋挺全的，應該直接看得懂，就不解釋了 寫的不好...只是希望能給視頻網站開發的新手一點點幫助吧. 業務場景：視頻分段傳輸、視頻多段傳輸（理 ......

    uj5u.com 2023-04-20 07:22:42 more
  • Windows 10開發教程_編程入門自學教程_菜鳥教程-免費教程分享

    教程簡介 Windows 10開發入門教程 - 從簡單的步驟了解Windows 10開發，從基本到高級概念，包括簡介，UWP，第一個應用程式，商店，XAML控制元件，資料系結，XAML性能，自適應設計，自適應UI，自適應代碼，檔案管理，SQLite資料庫，應用程式到應用程式通信，應用程式本地化，應用程式 ......

    uj5u.com 2023-04-20 07:22:35 more

Copyright © 2010-2020 有解無憂