国产 无码 综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

  1. Toy模板網(wǎng)首頁
  2. >Toy博客

數(shù)據(jù)結(jié)構(gòu)__＜八大排序＞ __插入排序 |希爾排序 |選擇排序 |堆排序 |快速排序 |歸并排序（C語言實現(xiàn)）

2年前作者：小黃同學(xué)LL分類：Toy博客閱讀(99)違法舉報

這篇具有很好參考價值的文章主要介紹了數(shù)據(jù)結(jié)構(gòu)__＜八大排序＞ __插入排序 |希爾排序 |選擇排序 |堆排序 |快速排序 |歸并排序（C語言實現(xiàn)）。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

目錄

插入排序?

希爾排序

選擇排序

堆排序

冒泡排序

快速排序

hoare法

挖坑法

前后指針法

快排特性總結(jié)

三數(shù)取中優(yōu)化

小區(qū)間優(yōu)化

快排非遞歸

歸并排序

歸并排序非遞歸

計數(shù)排序

總結(jié)

OJ測試

前言目錄

數(shù)據(jù)結(jié)構(gòu)__＜八大排序＞ __插入排序 |希爾排序 |選擇排序 |堆排序 |快速排序 |歸并排序（C語言實現(xiàn)）

插入排序?

數(shù)據(jù)結(jié)構(gòu)__＜八大排序＞ __插入排序 |希爾排序 |選擇排序 |堆排序 |快速排序 |歸并排序（C語言實現(xiàn)）

//直接插入排序
void InsertSort(int* a, int n)
{
	// i的取值范圍：[0,n-2]
	for (int i = 0; i < n - 1; i++)
	{
		//每一趟排序
		int end = i;
		int tmp = a[end + 1]; //將tmp視為插入的數(shù)字
		while (end >= 0)
		{
			if (tmp < a[end]) //若插入的數(shù)字小于有序數(shù)字的最后一個數(shù)
			{
				a[end + 1] = a[end]; //將大于tmp的值往后挪
				--end;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

1、元素集合越接近有序，直接插入排序算法的時間效率越高

2、時間復(fù)雜度：O(N^2)

3、空間復(fù)雜度：O(1)，它是一種穩(wěn)定的排序算法

4、穩(wěn)定性：穩(wěn)定

希爾排序

數(shù)據(jù)結(jié)構(gòu)__＜八大排序＞ __插入排序 |希爾排序 |選擇排序 |堆排序 |快速排序 |歸并排序（C語言實現(xiàn)）

?數(shù)據(jù)結(jié)構(gòu)__＜八大排序＞ __插入排序 |希爾排序 |選擇排序 |堆排序 |快速排序 |歸并排序（C語言實現(xiàn)）

//希爾排序
void ShellSort(int* a, int n)
{
	//1、gap > 1 預(yù)排序
	//2、gap == 1 直接插入排序
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1; //+1能夠保證最后一次gap一定是1
		                   //控制gap組都進行預(yù)排序


        //這里只是把插入排序的1換成gap即可
		//但是這里不是排序完一個分組，再去
		//排序另一個分組，而是整體只過一遍
		//這樣每次對于每組數(shù)據(jù)只排一部分
		//整個循環(huán)結(jié)束之后，所有組的數(shù)據(jù)排序完成
		for (int i = 0; i < n - gap; i++)
		{
			//確保一組中的數(shù)據(jù)都進行插入排序
			int end = i;
			//定義一個變量tmp保存end的后一個數(shù),其下標(biāo)是end+gap
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];//如果end下標(biāo)的數(shù)值大于后面的值tmp，也就意味著end下標(biāo)的值要往后挪
					end -= gap;
				}
				else
				{
					break;
				}
			}
			//單趟循環(huán)結(jié)束或循環(huán)中直接break出來均直接賦值
			a[end + gap] = tmp;
		}
	}
}

1、希爾排序是對直接插入排序的優(yōu)化。

2、當(dāng)gap > 1時都是預(yù)排序，目的是讓數(shù)組更接近于有序。當(dāng)gap == 1時，數(shù)組已經(jīng)接近有序的了，這樣就會很快。這樣整體而言，可以達到優(yōu)化的效果。我們實現(xiàn)后可以進行性能測試的對比。

3、穩(wěn)定性：不穩(wěn)定

4、時間復(fù)雜度分析：

?希爾排序的時間復(fù)雜度不是很好算，我們先簡要看下預(yù)排序的時間復(fù)雜度：

  1. gap很大時，數(shù)據(jù)跳的很快，里面套的循環(huán)可以忽略不記，差不多是O(N)。
  2. gap很小時，數(shù)據(jù)跳的很慢，很接近有序，差不多也是O(N)

再來看外面套上循環(huán)后的時間復(fù)雜度：

while循環(huán)中的gap = gap / 3 + 1相當(dāng)于是循環(huán)了次

既然外循環(huán)執(zhí)行次，內(nèi)循環(huán)執(zhí)行N次，那么時間復(fù)雜度為O()。但是上述計算頂多是估算，有人在大量的實驗基礎(chǔ)上推出其時間復(fù)雜度應(yīng)為：O()

選擇排序

數(shù)據(jù)結(jié)構(gòu)__＜八大排序＞ __插入排序 |希爾排序 |選擇排序 |堆排序 |快速排序 |歸并排序（C語言實現(xiàn)）

思路：

優(yōu)化的選擇排序，每次可以選擇一個最大的和一個最小的，然后把他們放在合適的位置，即最小的放在第一個位置，最大的放在最后一個位置，然后再去選擇次小的和次大的，依次這樣進行，直到區(qū)間只剩一個值或沒有

#include<iostream>
#include<string>
#include<stdlib.h> 
using namespace std;
 
//交換
void Swap(int* pa, int* pb)
{
	int tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}
void SelectSort(int* a, int n)
{
	//assert(a);
	int begin = 0, end = n - 1;
	while (begin < end)
	{
		int min = begin, max = begin;
		for (int i = begin; i <= end; i++)
		{
			if (a[i] >= a[max])
				max = i;
 
 
			if (a[i] < a[min])
				min = i;
		}
		//最小的放在
		Swap(&a[begin], &a[min]);
		//如果最大的位置在begin位置
		//說明min是和最大的交換位置
		//這個時候max的位置就發(fā)生了變換
		//max變到了min的位置
		//所以要更新max的位置
		if (begin == max)
			max = min;
 
 
		Swap(&a[end], &a[max]);
		++begin;
		--end;
 
 
		//PrintArray(a, n);
	}
}
void PrintArray(int a[], int sum)
{
	for(int i=0;i<sum;i++)
	{
		cout<<a[i]<<" ";
	}
	cout<<endl;
}
 
void TestSelectSort()
{
	int a[] = { 3, 4, 6, 1, 2, 8, 0, 5, 7 };
	SelectSort(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}
int main()
{
	TestSelectSort();
	return 0;
}

1、直接選擇排序思考非常好理解，但是效率不是很好。實際中很少使用

2、時間復(fù)雜度：O(N^2)

3、空間復(fù)雜度：O(1)

4、穩(wěn)定性：不穩(wěn)定

易錯題：?

使用選擇排序?qū)﹂L度為100的數(shù)組進行排序，則比較的次數(shù)為（ ）

A.5050

B.4950

C.4851

D.2475

答案：B

解析：

選擇排序，每次都要在未排序的所有元素中找到最值，

如果有n個元素，則

第一次比較次數(shù)： n - 1

第二次比較次數(shù)： n - 2

....

第n - 1次比較次數(shù)： 1

所有如果n = 100

則比較次數(shù)的總和：99 + 98 + ...... + 1

共4950次。

堆排序

1,建大堆,把根交換到最底,然后在減一個元素繼續(xù)調(diào)整

2,向下調(diào)整,繼續(xù)交換,直到最后一個元素

數(shù)據(jù)結(jié)構(gòu)__＜八大排序＞ __插入排序 |希爾排序 |選擇排序 |堆排序 |快速排序 |歸并排序（C語言實現(xiàn)）

?數(shù)據(jù)結(jié)構(gòu)__＜八大排序＞ __插入排序 |希爾排序 |選擇排序 |堆排序 |快速排序 |歸并排序（C語言實現(xiàn)）

上圖的代碼：?

void HeapSort(int* a, int n)
{
	//向下調(diào)整建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
	//大堆升序
	size_t end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);    //為了保持完全二叉樹狀態(tài)
		AdjustDown(a, end, 0);
		end--;
	}
}
#include<iostream>
#include<string>
#include<stdlib.h> 
using namespace std;
 
//交換
void Swap(int* pa, int* pb)
{
	int tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}
//向下調(diào)整算法
void AdjustDown(int* a, size_t size, size_t root)
{
	int parent = (int)root;
	int child = 2 * parent + 1;
	while (child < size)
	{
		//1、確保child的下標(biāo)對應(yīng)的值最大，即取左右孩子較大那個
		if (child + 1 < size && a[child + 1] > a[child]) //得確保右孩子存在
		{
			child++; //此時右孩子大
		}
		//2、如果孩子大于父親則交換，并繼續(xù)往下調(diào)整
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}
//升序
void HeapSort(int* a, int n)
{
	//向下調(diào)整建堆
    // 建堆，先從最后兩個葉子上的根(索引為(n - 2) / 2開始建堆
	// 先建最小的堆，直到a[0](最大的堆)
	// 這就相當(dāng)于在已經(jīng)建好的堆上面，新加入一個
	// 根元素，然后向下調(diào)整，讓整個完全二叉樹
	// 重新滿足堆的性質(zhì)
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
	//大堆升序
	size_t end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		end--;
	}
}
int main()
{
	int a[] = { 4,2,7,8,5,1,0,6 };
	HeapSort(a, sizeof(a) / sizeof(int));
	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		printf("%d ", a[i]);
	}
	return 0;
}

1、堆排序使用堆來選數(shù)，效率就高了很多。

2、時間復(fù)雜度：O(N*logN)

3、空間復(fù)雜度：O(1)

4、穩(wěn)定性：不穩(wěn)定

冒泡排序

數(shù)據(jù)結(jié)構(gòu)__＜八大排序＞ __插入排序 |希爾排序 |選擇排序 |堆排序 |快速排序 |歸并排序（C語言實現(xiàn)）

//交換
void Swap(int* pa, int* pb)
{
	int tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}
//冒泡排序
void BubbleSort(int* a, int n)
{
	for (int j = 0; j < n; j++)
	{
		for (int i = 1; i < n - j; i++)
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i], &a[i - 1]);
			}
			
		}
	}
}

1、冒泡排序是一種非常容易理解的排序

2、穩(wěn)定性：穩(wěn)定

3、空間復(fù)雜度：O(1)

4、時間復(fù)雜度：O(N^2)

最好情況：數(shù)組本身是順序的，外層循環(huán)遍歷一次就完成

最壞情況：數(shù)組本身是逆序的，內(nèi)外層遍歷

快速排序

hoare法

數(shù)據(jù)結(jié)構(gòu)__＜八大排序＞ __插入排序 |希爾排序 |選擇排序 |堆排序 |快速排序 |歸并排序（C語言實現(xiàn)）

  1. 選出一個key，一般是第一個數(shù)，或者是最后一個數(shù)
  2. 定義變量L和R，L從左走，R從右走
  3. R先向前走，找到比key小的位置停下，再讓L向后走，找到比key大的值停下
  4. 交換L和R代表的數(shù)值
  5. 繼續(xù)遍歷，同樣讓R先走，L后走，同上規(guī)則
  6. 當(dāng)L和R相遇的時候，把相遇位置的值與key位置的值交換，結(jié)束
//hoare
//快排單趟排序
int PartSort(int* a, int left, int right)
{
	int keyi = left; //選左邊作key
	while (left < right)
	{
		//右邊先走，找小
		while (left < right && a[right] >= a[keyi]) //防止right找不到比keyi小的值直接飆出去，要加上left < right
		{
			right--;
		}
		//右邊找到后，左邊再走，找大
		while (left < right && a[left] <= a[keyi]) //同上，也要加上left < right
		{
			left++;
		}
		//右邊找到小，左邊找到大，就交換
		Swap(&a[left], &a[right]);
	}
	//此時left和right相遇，交換與key的值
	Swap(&a[keyi], &a[left]);
	return left;
}
 
//快速排序
void QuickSort(int* a, int begin, int end)
{
	//子區(qū)間相等只有一個值或者不存在那么就是遞歸結(jié)束的子問題
	if (begin >= end)
	{
		return;
	}
	int keyi = PartSort(a, begin, end);
	//分成左右兩段區(qū)間遞歸
	// [begin, keyi-1] 和 [keyi+1, end]
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

挖坑法

數(shù)據(jù)結(jié)構(gòu)__＜八大排序＞ __插入排序 |希爾排序 |選擇排序 |堆排序 |快速排序 |歸并排序（C語言實現(xiàn)）

  1. ?把最左邊的位置用key保存起來，此位置形成坑位
  2. 定義變量L和R分別置于最左和最右
  3. 讓R先向前走，找到比key小的位置停下
  4. 找到后，將該值放入坑位，自己形成新的坑位
  5. 再讓L向后走，找比key大的位置停下
  6. 找到后，將該值放入坑位，自己形成新的坑位
  7. 再讓R走……
  8. 當(dāng)L和R相遇時，把key的值放到坑位，結(jié)束
    ?
//挖坑法
int PartSort2(int* a, int left, int right)
{
	//把最左邊的值用key保存起來
	int key = a[left]; 
	//把left位置設(shè)為坑位pit
	int pit = left;
	while (left < right) //當(dāng)left小于right時就繼續(xù)
	{
		//右邊先走，找小于key的值
		while (left < right && a[right] >= key)
		{
			right--; //如若right的值>=key的值就繼續(xù)
		}
		//找到小于key的值時就把此位置賦到坑位，并把自己置為新的坑位
		a[pit] = a[right];
		pit = right;
 
		//左邊走，找大于key的值
		while (left < right && a[left] <= key)
		{
			left++;
		}
		//找到大于key的值就把此位置賦到坑位，并把自己置為新的坑位
		a[pit] = a[left];
		pit = left;
	}
	//此時L和R相遇，將key賦到坑位
	a[pit] = key;
	return pit;
}
 
//快速排序
void QuickSort(int* a, int begin, int end)
{
	//子區(qū)間相等只有一個值或者不存在那么就是遞歸結(jié)束的子問題
	if (begin >= end)
	{
		return;
	}
	int keyi = PartSort2(a, begin, end);
	//分成左右兩段區(qū)間遞歸
	// [begin, keyi-1] 和 [keyi+1, end]
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

前后指針法

數(shù)據(jù)結(jié)構(gòu)__＜八大排序＞ __插入排序 |希爾排序 |選擇排序 |堆排序 |快速排序 |歸并排序（C語言實現(xiàn)）

  1. 把第一個位置的值設(shè)為key保存起來
  2. 定義prev指針指向第一個位置，cur指向prev后一個位置
  3. 若cur指向的數(shù)值小于key，prev和cur均后移
  4. 當(dāng)cur指向的數(shù)據(jù)大于key時，prev不動，cur繼續(xù)后移
  5. 當(dāng)cur的值小于key時，prev后移一位，交換與cur的值，cur再++
  6. 重復(fù)上述操作，當(dāng)cur越界時，交換此時的prev和key的值。結(jié)束
    ?
//前后指針法
int PartSort3(int* a, int left, int right)
{
	int key = left;//注意不能寫成 int key = a[left]
	int prev = left;
	int cur = prev + 1;
	while (cur <= right)
	{
		if (a[cur] < a[key] && a[++prev] != a[cur]) 
		{
			Swap(&a[prev], &a[cur]);//在cur的值小于key的值的前提下，并且prev后一個值不等于cur的值時交換，避免了交換兩個小的（雖然也可以，但是沒有意義）
		}
		cur++; //如若cur的值大于key，則cur++
	}
	Swap(&a[prev], &a[key]); //此時cur越界，直接交換key與prev位置的值
	return prev;
}
 
//快速排序
void QuickSort(int* a, int begin, int end)
{
	//子區(qū)間相等只有一個值或者不存在那么就是遞歸結(jié)束的子問題
	if (begin >= end)
	{
		return;
	}
	int keyi = PartSort2(a, begin, end);
	//分成左右兩段區(qū)間遞歸
	// [begin, keyi-1] 和 [keyi+1, end]
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

快排特性總結(jié)

穩(wěn)定性：不穩(wěn)定

空間復(fù)雜度：O(logN)

時間復(fù)雜度：O(N*logN)

快排的時間復(fù)雜度分兩種情況討論：

  1. 最好：每次選key都是中位數(shù)，通俗講是左邊一半右邊一半，具體看是key的左序列長度和右序列長度相同。時間復(fù)雜度O(N*logN)
  2. 最壞：每次選出最小的或者最大的作為key。時間復(fù)雜度O()

易錯題：

排序過程中，對尚未確定最終位置的所有元素進行一遍處理稱為一“趟”。下列排序中，不可能是快速排序第二趟結(jié)果的是（）【2019年全國試題10（2分）】

A. 5, 2, 16, 12, 28, 60, 32, 72
B. 2, 16, 5, 28, 12, 60, 32, 72
C. 2, 12, 16, 5, 28, 32, 72, 60
D. 5, 2, 12, 28, 16, 32, 72, 60

答案：D

每經(jīng)過一趟快排，軸點元素都必然就位。也就是說，一趟下來至少有1個元素在其最終位置。所以考察各個選項，看有幾個元素就位即可。

最終排序位置是：2, 5, 12, 16, 28, 32, 60, 72，而選項中正確的位置有：

A. 5, 2, 16, 12, 28, 60, 32, 72
B. 2, 16, 5, 28, 12, 60, 32, 72
C. 2, 12, 16, 5, 28, 32, 72, 60
D. 5, 2, 12, 28, 16, 32, 72, 60


對于D選項，在第一趟排序好，一定能確定一個樞軸元素，要么是12，要么是32，如果是12的話，在第二趟向左遞歸的時候，一定是2排在5的前面,如果第二趟是先向右遞歸，那么16肯定排在28的前面,。如果是32的話，跟上面的一個思路,在第二趟排序的時候,如果先向左遞歸，5一定排在2的后面，如果先向右遞歸，60也一定排到72的前面，綜上，這兩種情況d選項都不符合。

三數(shù)取中優(yōu)化

取第一個數(shù)，最后一個數(shù)，中間那個數(shù)，在這三個數(shù)中選不是最大也不是最小的那個數(shù)作為key。此法針對有序瞬間從最壞變成最好，針對隨機數(shù)，那么選出來的數(shù)也同樣不是最大也不是最小，同樣進行了優(yōu)化。

三數(shù)取中其實針對hoare法，挖坑法，前后指針法都適用，這里我們就以前后指針法示例：

//快排
//三數(shù)曲中優(yōu)化
int GetMidIndex(int* a, int left, int right)
{
	int mid = (left + right) / 2; // int mid = left + (right - left) / 2
	// left  mid  right
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right]) // left < mid < right
			return mid;
		else if (a[left] < a[right]) // left < right <mid
			return right;
		else  // right < left < mid
			return left; 
	}
	else // left > mid
	{
		if (a[right] > a[left]) // right > left > mid
			return left;
		else if (a[mid] > a[right])// left > mid > right
			return mid;
		else // left > right > mid
			return right;
	}
}
 
//前后指針法
int PartSort3(int* a, int left, int right)
{
	//三數(shù)取中優(yōu)化
	int midi = GetMidIndex(a, left, right);
	Swap(&a[midi], &a[left]);
 
	int key = left;//注意不能寫成 int key = a[left]
	int prev = left;
	int cur = prev + 1;
	while (cur <= right)
	{
		if (a[cur] < a[key] && a[++prev] != a[cur]) 
		{
			Swap(&a[prev], &a[cur]); 
		}
		cur++;  
	}
	Swap(&a[prev], &a[key]);  
	return prev;
}
 
//快速排序
void QuickSort(int* a, int begin, int end)
{
	//子區(qū)間相等只有一個值或者不存在那么就是遞歸結(jié)束的子問題
	if (begin >= end)
	{
		return;
	}
	int keyi = PartSort3(a, begin, end);
	//分成左右兩段區(qū)間遞歸
	// [begin, keyi-1] 和 [keyi+1, end]
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

小區(qū)間優(yōu)化

當(dāng)遞歸到越小的區(qū)間時，遞歸次數(shù)就會越多，針對這一小區(qū)間采取插入排序更優(yōu)，減少了大量的遞歸次數(shù)

//三數(shù)取中優(yōu)化
int GetMidIndex(int* a, int left, int right)
{
    //……
}
 
//前后指針法
int PartSort3(int* a, int left, int right)
{
	//三數(shù)取中優(yōu)化
	int midi = GetMidIndex(a, left, right);
	Swap(&a[midi], &a[left]);
    //……
}
 
//小區(qū)間優(yōu)化
void QuickSort2(int* a, int begin, int end)
{
	//子區(qū)間相等只有一個值或者不存在那么就是遞歸結(jié)束的子問題
	if (begin >= end)
	{
		return;
	}
	//小區(qū)間直接插入排序控制有序
	if (end - begin + 1 <= 10)
	{
		InsertSort(a + begin, end - begin + 1);
	}
	else
	{
		int keyi = PartSort3(a, begin, end);
		// [begin, keyi-1] 和 [keyi+1, end]
		QuickSort(a, begin, keyi - 1);
		QuickSort(a, keyi + 1, end);
	}
}

快排非遞歸

在快排遞歸的過程中是要建立棧幀的，仔細(xì)看看每次遞歸時傳的參數(shù)，有begin和end，其遞歸過程存儲的是排序過程中要控制的區(qū)間，那我們用非遞歸模擬遞歸的過程中也要按照它這個存儲方式進行，這就需要借助棧了

//快排非遞歸
void QuickSort3(int* a, int begin, int end)
{
	ST st;
	StackInit(&st);
	//先把第一塊區(qū)間入棧
	StackPush(&st, begin);
	StackPush(&st, end);
	while (!StackEmpty(&st)) //棧不為空就繼續(xù)
	{
		int right = StackTop(&st);
		StackPop(&st);
		int left = StackTop(&st);
		StackPop(&st);
 
		//使用前后指針法進行排序
		int keyi = PartSort3(a, left, right); // keyi已經(jīng)到了正確位置
 
		// [left, kryi-1]  [keyi+1, right]
		if (left < keyi - 1)//如若左區(qū)間不只一個數(shù)就入棧
		{
			StackPush(&st, left);
			StackPush(&st, keyi - 1);
		}
		if (keyi + 1 < right)//若右區(qū)間不只一個就入棧
		{
			StackPush(&st, keyi + 1);
			StackPush(&st, right);
		}
	}
	StackDestory(&st);
}

數(shù)據(jù)結(jié)構(gòu)__＜八大排序＞ __插入排序 |希爾排序 |選擇排序 |堆排序 |快速排序 |歸并排序（C語言實現(xiàn)）

歸并排序

數(shù)據(jù)結(jié)構(gòu)__＜八大排序＞ __插入排序 |希爾排序 |選擇排序 |堆排序 |快速排序 |歸并排序（C語言實現(xiàn)）

數(shù)據(jù)結(jié)構(gòu)__＜八大排序＞ __插入排序 |希爾排序 |選擇排序 |堆排序 |快速排序 |歸并排序（C語言實現(xiàn)）

如圖所示，先分為最小單元，利用數(shù)組tmp排序，然后回溯重復(fù)操作?

void _MergeSort(int* a, int begin, int end, int* tmp)
{
	if (begin >= end)
		return; //區(qū)間不存在就返回
	int mid = (begin + end) / 2;
	//[begin, mid] [mid+1, end]
	_MergeSort(a, begin, mid, tmp); //遞歸左半
	_MergeSort(a, mid + 1, end, tmp); //遞歸右半
 
	//歸并[begin, mid] [mid+1, end]
	//printf("歸并[%d,%d][%d,%d]\n", begin, mid, mid + 1, end);
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int index = begin;
	while (begin1 <= end1 && begin2 <= end2)
	{
		//將較小的值放到tmp數(shù)組里頭
		if (a[begin1] < a[begin2])
		{
			tmp[index++] = a[begin1++];
		}
		else
		{
			tmp[index++] = a[begin2++];
		}
	}
	//如若begin2先走完，把begin1后面的元素拷貝到新數(shù)組
	while (begin1 <= end1)
	{
		tmp[index++] = a[begin1++];
	}
	//如若begin1先走完，把begin2后面的元素拷貝到新數(shù)組
	while (begin2 <= end2)
	{
		tmp[index++] = a[begin2++];
	}
	//歸并結(jié)束后，把tmp數(shù)組拷貝到原數(shù)組
	memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}
 
//歸并排序
void MergeSort(int* a, int n)
{
	//malloc一塊新數(shù)組
	int* tmp = (int*)malloc(sizeof(int) * n);
	assert(tmp);
	_MergeSort(a, 0, n - 1, tmp);
	free(tmp);
}

?1、歸并的缺點在于需要O(N)的空間復(fù)雜度，歸并排序的思考更多的是解決在磁盤中的外排序問題。

2、時間復(fù)雜度：O(N*logN)

3、空間復(fù)雜度：O(N)

4、穩(wěn)定性：穩(wěn)定?

歸并排序非遞歸

  • 思想：

歸并的非遞歸不需要借助棧，直接使用循環(huán)即可。遞歸版中我們是對數(shù)組進行劃分成最小單位，這里非遞歸我們直接把它看成最小單位進行歸并。我們可以通過控制間距gap來完成

//歸并非遞歸
void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	assert(tmp);
	int gap = 1;
	while (gap < n)
	{
		//分組歸并，間距為gap是一組，兩兩歸并
		for (int i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
			//end1越界，修正即可
			if (end1 >= n)
			{
				end1 = n - 1;
			}
			//begin2越界，第二個區(qū)間不存在
			if (begin2 >= n)
			{
				begin2 = n;
				end2 = n - 1;
			}
			//begin2 ok，end2越界，修正下end2即可
			if (begin2 < n && end2 >= n)
			{
				end2 = n - 1;
			}
			printf("歸并[%d,%d][%d,%d]\n", begin1, end1, begin2, end2);
			int index = i;
			while (begin1 <= end1 && begin2 <= end2)
			{
				//將較小的值放到tmp數(shù)組里頭
				if (a[begin1] < a[begin2])
				{
					tmp[index++] = a[begin1++];
				}
				else
				{
					tmp[index++] = a[begin2++];
				}
			}
			//如若begin2先走完，把begin1后面的元素拷貝到新數(shù)組
			while (begin1 <= end1)
			{
				tmp[index++] = a[begin1++];
			}
			//如若begin1先走完，把begin2后面的元素拷貝到新數(shù)組
			while (begin2 <= end2)
			{
				tmp[index++] = a[begin2++];
			}
		}
		memcpy(a, tmp, n * sizeof(int));
		gap *= 2;
	}
	free(tmp);
}

優(yōu)化+完整版?


/*
非遞歸排序與遞歸排序相反，將一個元素與相鄰元素構(gòu)成有序數(shù)組，
再與旁邊數(shù)組構(gòu)成有序數(shù)組，直至整個數(shù)組有序。
要有mid指針傳入，因為不足一組數(shù)據(jù)時，重新計算mid劃分會有問題
需要指定mid的位置
*/
void merge(int* a, int left, int mid, int right, int* tmp)
{
	// [left, mid]
	// [mid+1, right]
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int index = left;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] <= a[begin2])
			tmp[index++] = a[begin1++];
		else
			tmp[index++] = a[begin2++];
	}
 
	while (begin1 <= end1)
	{
		tmp[index++] = a[begin1++];
	}
 
	while (begin2 <= end2)
	{
		tmp[index++] = a[begin2++];
	}
 
	memcpy(a+left, tmp+left, sizeof(int)*(right - left+1));
}
 
/*
k用來表示每次k個元素歸并
*/
void mergePass(int *arr, int k, int n, int *temp)
{
  int i = 0;
  //從前往后,將2個長度為k的子序列合并為1個
  while(i < n - 2*k + 1)
  {
    merge(arr, i, i + k - 1, i + 2*k - 1, temp);
    i += 2*k;
  }
  //合并區(qū)間[i, n - 1]有序的左半部分[i, i + k - 1]以及不及一個步長的右半部分[i + k, n - 1]
  if(i < n - k )
  {
    merge(arr, i, i + k - 1,n-1, temp);
  }
   
}
 
// 歸并排序非遞歸版
void MergeSortNonR(int *arr,int length)
{
  int k = 1;
  int *temp = (int *)malloc(sizeof(int) * length);
  while(k < length)
  {
    mergePass(arr, k, length, temp);
    k *= 2;
  }
  free(temp);
}
 
void TestMergeSort()
{
	int a[] = { 3, 4, 6, 1, 2, 8, 0, 5, 7 };
	MergeSort(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}

?1、歸并的缺點在于需要O(N)的空間復(fù)雜度，歸并排序的思考更多的是解決在磁盤中的外排序問題。

2、時間復(fù)雜度：O(N*logN)

3、空間復(fù)雜度：O(N)

4、穩(wěn)定性：穩(wěn)定?

計數(shù)排序

數(shù)據(jù)結(jié)構(gòu)__＜八大排序＞ __插入排序 |希爾排序 |選擇排序 |堆排序 |快速排序 |歸并排序（C語言實現(xiàn)）

  • 絕對映射：原數(shù)組是幾，映射到新數(shù)組下標(biāo)位置++
  • 相對映射：此時新數(shù)組下標(biāo)的范圍是從0到原數(shù)組最小的值，而映射到下標(biāo)的位置為原數(shù)組val的值 - 原數(shù)組最小min的值
//計數(shù)排序
void CountSort(int* a, int n)
{
	int min = a[0], max = a[0];
	//先求出原數(shù)組的最大和最小值
	for (int i = 1; i < n; i++)
	{
		if (a[i] < min)
			min = a[i];
		if (a[i] > max)
			max = a[i];
	}
	//求出新數(shù)組的范圍
	int range = max - min + 1;
	//開辟新數(shù)組
	int* countA = (int*)malloc(sizeof(int) * range);
	assert(countA);
	//把新開辟數(shù)組初始化為0
	memset(countA, 0, sizeof(int) * range);
 
	//計數(shù)
	for (int i = 0; i < n; i++)
	{
		countA[a[i] - min]++; //統(tǒng)計相同元素出現(xiàn)次數(shù)（相對映射）
	}
 
	//排序
	int j = 0;
	for (int i = 0; i < range; i++)
	{
		while (countA[i]--)
		{
			a[j++] = i + min; //賦值時，記得加回原先的min
		}
	}
	free(countA);
}

完整版?

void CountSort(int* a, int n)
{
	int max = a[0], min = a[0];
	for (int i = 0; i < n; ++i)
	{
		if (a[i] > max)
			max = a[i];
 
		if (a[i] < min)
			min = a[i];
	}
	//找到數(shù)據(jù)的范圍
	int range = max - min + 1;
	int* countArray = (int*)malloc(range*sizeof(int));
	memset(countArray, 0, sizeof(int)*range);
	//存放在相對位置，可以節(jié)省空間
	for (int i = 0; i < n; ++i)
	{
		countArray[a[i] - min]++;
	}
	//可能存在重復(fù)的數(shù)據(jù)，有幾個存幾個
	int index = 0;
	for (int i = 0; i < range; ++i)
	{	
		while (countArray[i]--)
		{
			a[index++] = i+min;
		}
	}
}
 
void TestCountSort()
{
	int a[] = { 3, 4, 6, 2, 8, 5, 2, 2, 9, 9, 1000000, 99999};
	CountSort(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}
 
void TestSortOP()
{
	const int n = 1000000;
	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);
	int* a8 = (int*)malloc(sizeof(int)*n);
 
	srand(time(0));
	for (int i = 0; i < n; ++i)
	{
		a1[i] = rand();
		a2[i] = a1[i];
		a3[i] = a1[i];
		a4[i] = a1[i];
		a5[i] = a1[i];
		a6[i] = a1[i];
		a7[i] = a1[i];
		a8[i] = a1[i];
	}
	a8[n] = 100000000;
 
	size_t begin1 = clock();
	//InsertSort(a1, n);
	size_t end1 = clock();
	printf("%u\n", end1 - begin1);
 
	size_t begin2 = clock();
	ShellSort(a2, n);
	size_t end2 = clock();
	printf("%u\n", end2 - begin2);
 
	size_t begin3 = clock();
	//SelectSort(a3, n);
	size_t end3 = clock();
	printf("%u\n", end3 - begin3);
 
	size_t begin4 = clock();
	HeapSort(a4, n);
	size_t end4 = clock();
	printf("%u\n", end4 - begin4);
	
	size_t begin5 = clock();
	//BubbleSort(a5, n);
	size_t end5 = clock();
	printf("%u\n", end5 - begin5);
 
	size_t begin6 = clock();
	QuickSort(a6, 0, n-1);
	size_t end6 = clock();
	printf("%u\n", end6 - begin6);
 
	size_t begin7 = clock();
	MergeSort(a7, n);
	size_t end7 = clock();
	printf("%u\n", end7 - begin7);
 
	size_t begin8 = clock();
	CountSort(a8, n);
	size_t end8 = clock();
	printf("%u\n", end8 - begin8);
}
  1. 計數(shù)排序在數(shù)據(jù)范圍集中時，效率很高，但是適用范圍及場景有限。
  2. 時間復(fù)雜度：O(N + range)
  3. 空間復(fù)雜度：O(range)
  4. 穩(wěn)定性：穩(wěn)定

總結(jié)

  • 內(nèi)排序：數(shù)據(jù)量較少，在內(nèi)存中進行排序
  • 外排序：數(shù)據(jù)量很大，在磁盤上進行排序
  • 綜上1G = 1024*1024*1024Byte，而10億個整數(shù)40億Byte，所以10億個整數(shù)占4G，即1e9以下可內(nèi)排序，以上必須外排序

數(shù)據(jù)結(jié)構(gòu)__＜八大排序＞ __插入排序 |希爾排序 |選擇排序 |堆排序 |快速排序 |歸并排序（C語言實現(xiàn)）

數(shù)據(jù)結(jié)構(gòu)__＜八大排序＞ __插入排序 |希爾排序 |選擇排序 |堆排序 |快速排序 |歸并排序（C語言實現(xiàn)）

OJ測試

912. 排序數(shù)組 - 力扣（LeetCode）

?文章來源地址http://www.zghlxwxcb.cn/news/detail-408966.html

/*
此題對于時間效率要求較高，像插入排序，選擇排序，冒泡排序都是O(n^2)的時間復(fù)雜度，所以這三種排序都跑不過。
*/
int* sortArray(int* nums, int numsSize, int* returnSize){
    //插入排序， 此題如果用插入排序，時間復(fù)雜度過高，會導(dǎo)致TLE
    InsertSort(nums, numsSize);
    //希爾
    ShellSort(nums, numsSize);
    //選擇，會超出時間限制
    SelectSort(nums, numsSize);
    //冒泡排序, 也會超出時間限制
    BubbleSort(nums, numsSize);
    //快排
    QuickSort(nums, 0, numsSize - 1);
    //歸并
    MergeSort(nums, numsSize);
    //計數(shù)
    CountSort(nums, numsSize);
    
    *returnSize = numsSize;
    return nums;
}

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)__＜八大排序＞ __插入排序 |希爾排序 |選擇排序 |堆排序 |快速排序 |歸并排序（C語言實現(xiàn)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！

本文來自互聯(lián)網(wǎng)用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務(wù)，不擁有所有權(quán)，不承擔(dān)相關(guān)法律責(zé)任。如若轉(zhuǎn)載，請注明出處： 如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實不符，請點擊違法舉報進行投訴反饋，一經(jīng)查實，立即刪除！

領(lǐng)支付寶紅包贊助服務(wù)器費用

相關(guān)文章

覺得文章有用就打賞一下文章作者

支付寶掃一掃打賞

博客贊助

微信掃一掃打賞

請作者喝杯咖啡吧~博客贊助

支付寶掃一掃領(lǐng)取紅包，優(yōu)惠每天領(lǐng)

二維碼1

領(lǐng)取紅包

二維碼2

領(lǐng)紅包