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

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

數(shù)據(jù)結(jié)構(gòu)排序——詳解快排及其優(yōu)化和冒泡排序(c語言實現(xiàn)、附有圖片與動圖示意）

2年前作者：是Nero哦分類：Toy博客閱讀(22)違法舉報

這篇具有很好參考價值的文章主要介紹了數(shù)據(jù)結(jié)構(gòu)排序——詳解快排及其優(yōu)化和冒泡排序(c語言實現(xiàn)、附有圖片與動圖示意）。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

上次講了選擇排序和堆排序：數(shù)據(jù)結(jié)構(gòu)排序——選擇排序與堆排序

今天就來快排和冒泡

1.快排

1.1基本介紹

快速排序（Quick Sort）是一種常用的排序算法，它是由英國計算機科學家Tony Hoare于1959年發(fā)明的?？焖倥判虻幕舅枷胧峭ㄟ^分治的策略將一個數(shù)組分成兩個子數(shù)組，然后分別對這兩個子數(shù)組進行排序。具體步驟如下：

  1. 選擇一個基準元素（通常是數(shù)組的第一個元素，右邊先行）。
  2. 將數(shù)組分割成兩部分，使得左邊的元素都小于等于基準元素，右邊的元素都大于基準元素。這個過程叫做分區(qū)（Partition）
  3. 對分割后的兩個子數(shù)組分別重復步驟1和2（利用遞歸），直到子數(shù)組的大小為1或0，此時數(shù)組已經(jīng)有序

==優(yōu)化：==如果本身就很接近有序，那效率就慢了（一個逆序變升序，keyi就一直在左邊，遞歸也只有右側(cè)，所以選擇三個數(shù)來找中間大小，能讓keyi盡量向數(shù)組中間靠近），所以設計了Getmid函數(shù)來取中間大小的數(shù)

1.2不同的分區(qū)方法及代碼實現(xiàn)

1.2.1Hoare版

使用兩個索引，一個從數(shù)組的左邊開始向右移動，另一個從數(shù)組的右邊開始向左移動，直到它們相遇。在這個過程中，如果左指針指向的元素大于基準元素且右指針指向的元素小于基準元素，則交換這兩個元素。當兩個指針相遇時，將基準元素（keyi指向的）與相遇位置的元素交換，這樣基準元素就歸位了

數(shù)據(jù)結(jié)構(gòu)排序——詳解快排及其優(yōu)化和冒泡排序(c語言實現(xiàn)、附有圖片與動圖示意）,數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)——排序,數(shù)據(jù)結(jié)構(gòu),算法,c++,java,機器學習,人工智能,c語言

void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

int GetMid(int* a,int left, int right)//找中間的
{
	// a[left]      a[mid]           a[right]
	int mid = (left + right) / 2;
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])  // mid是最大值
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else // a[left] > a[mid]
	{
		if (a[left] < a[right])
		{
			return left;
		}
		else if (a[mid] < a[right])
		{
			return right;
		}
		else
		{
			return mid;
		}
	}
}
//一次排序
int OneSort1(int* a, int left, int right)//使keyi位置的元素處于正確的位置上
{
	int mid = GetMid(a, left, right);
	Swap(&a[mid], &a[left]);//現(xiàn)在left處是三者的中間值了
	//左邊第一個為key，右邊先走才能保證相遇處比啊a[keyi]小
	int keyi = left;
	while (left < right)
	{
		while (a[right] >= a[keyi] && left < right)//右邊先走
		{
			right--;
		}
		while (a[left] <= a[keyi] && left < right)//左側(cè)找大的
		{
			left++;
		}
		Swap(&a[left], &a[right]);//找到一個大和一個小的就交換
	}
	Swap(&a[keyi], &a[left]);//把keyi放相遇位置
	return left;//返回相遇的索引
}

void QuickSort(int* a, int begin, int end)//升序
{
	if (begin >= end)
	{
		return;
	}
	// [begin, keyi-1] keyi [keyi+1, end]
	int keyi = OneSort1(a, begin, end);//找到keyi索引，才能分左右
	QuickSort(a, begin, keyi - 1);//左側(cè)
	QuickSort(a, keyi + 1, end);//右側(cè)
}

int main()
{
	int a[] = { 6,1,2,7,9,3,4,5,10,8 };
	printf("排序前：");
	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
	QuickSort(a, 0,sizeof(a) / sizeof(int)-1);
	printf("排序后：");
	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
	return 0;
}

數(shù)據(jù)結(jié)構(gòu)排序——詳解快排及其優(yōu)化和冒泡排序(c語言實現(xiàn)、附有圖片與動圖示意）,數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)——排序,數(shù)據(jù)結(jié)構(gòu),算法,c++,java,機器學習,人工智能,c語言

1.2.2挖坑版

選擇基準元素后，先將基準元素保存到臨時變量中，然后使用左右索引的方式找到需要交換的元素，將這些元素填入基準元素的位置，最后將基準元素填入最后一個空出來的位置

數(shù)據(jù)結(jié)構(gòu)排序——詳解快排及其優(yōu)化和冒泡排序(c語言實現(xiàn)、附有圖片與動圖示意）,數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)——排序,數(shù)據(jù)結(jié)構(gòu),算法,c++,java,機器學習,人工智能,c語言

int OneSort2(int* a, int left, int right)//挖坑
{
	int mid = GetMid(a, left, right);
	Swap(&a[mid], &a[left]);//現(xiàn)在left處是三者的中間值了

	int key = a[left];//保存基準元素
	int hole = left;//儲存坑下標，不能直接賦值為0
	while (left < right)
	{
		while (a[right] >= key && left < right)//右邊先走,沒有等號兩側(cè)出現(xiàn)相同值會死循環(huán)
		{
			right--;
		}//找到了就去賦值到第一個“坑”
		a[hole] = a[right];
		hole = right;//更新坑
		while (a[left] <= key && left < right)//左側(cè)找大的
		{
			left++;
		}
		a[hole] = a[left];
		hole = left;
	}
	Swap(&key, &a[left]);//把keyi放相遇位置
	return left;//返回相遇的索引
}

1.2.3 前后指針版

pre指向第一個，cur指向下一個。cur找小后，pre++，然后交換（做到大的向后推），最后cur出數(shù)組結(jié)束

prev的情況有兩種：

  1. 在cur還沒遇到比key大的值時候，prev緊跟著cur
  2. 在cur還遇到比key大的值時候，prev在比key大的一組值的前面

本質(zhì)是把一段大于key的區(qū)間，往后推，同時小的甩到左邊去

數(shù)據(jù)結(jié)構(gòu)排序——詳解快排及其優(yōu)化和冒泡排序(c語言實現(xiàn)、附有圖片與動圖示意）,數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)——排序,數(shù)據(jù)結(jié)構(gòu),算法,c++,java,機器學習,人工智能,c語言
數(shù)據(jù)結(jié)構(gòu)排序——詳解快排及其優(yōu)化和冒泡排序(c語言實現(xiàn)、附有圖片與動圖示意）,數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)——排序,數(shù)據(jù)結(jié)構(gòu),算法,c++,java,機器學習,人工智能,c語言

int OneSort3(int* a, int left, int right)//挖坑
{
	int mid = GetMid(a, left, right);
	Swap(&a[mid], &a[left]);

	int keyi = left;
	int pre = left;
	int cur = left + 1;
	while (cur <= right)
	{
		if (a[cur] < a[keyi])
		{
			pre++;
			Swap(&a[cur], &a[pre]);
		}
		cur++;
	}
	Swap(&a[pre], &a[keyi]);
	return pre;
}

1.3快排的優(yōu)化

1.3.1三數(shù)取中選key

從待排序數(shù)組的首、尾和中間位置各選取一個元素，然后取它們的中間值作為基準元素，確保選擇的基準元素相對中間位置的元素更為接近

代碼在Hoare版已經(jīng)展示過了

int GetMid(int* a,int left, int right)//找中間的
{
	// a[left]      a[mid]           a[right]
	int mid = (left + right) / 2;
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])  // mid是最大值
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else // a[left] > a[mid]
	{
		if (a[left] < a[right])
		{
			return left;
		}
		else if (a[mid] < a[right])
		{
			return right;
		}
		else
		{
			return mid;
		}
	}
}

1.3.2遞歸到小的子區(qū)間時，可以考慮使用插入排序

當遞歸到小的子區(qū)間時，可以考慮使用插入排序來優(yōu)化快速排序。因為插入排序在小規(guī)模數(shù)據(jù)上的排序效率通常比快速排序更高==(當數(shù)量比較少時，也沒必要在遞歸好幾層了)==

void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
			}
			else
			{
				break;
			}
			end--;
		}
		a[end + 1] = tmp;
	}
}

int OneSort3(int* a, int left, int right)//挖坑
{
	int mid = GetMid(a, left, right);
	Swap(&a[mid], &a[left]);

	int keyi = left;
	int pre = left;
	int cur = left + 1;
	while (cur <= right)
	{
		if (a[cur] < a[keyi])
		{
			pre++;
			Swap(&a[cur], &a[pre]);
		}
		cur++;
	}
	Swap(&a[pre], &a[keyi]);
	return pre;
}

void QuickSort(int* a, int begin, int end)//升序
{
	if (begin >= end)
	{
		return;
	}

	if ((end - begin + 1) > 10)
	{
		// [begin, keyi-1] keyi [keyi+1, end]
		int keyi = OneSort3(a, begin, end);
		QuickSort(a, begin, keyi - 1);
		QuickSort(a, keyi + 1, end);
	}
	else
	{
		//用插入排序
		InsertSort(a + begin, end - begin + 1);
	}
}

1.3.3大量重復數(shù)據(jù)采用三路劃分

快速排序的三路劃分通過將數(shù)組分為小于、等于=和大于基準元素的三個部分==，有效地處理了重復元素，提高了算法的效率

快速排序的三路劃分算法的基本思想是使用三個指針/下標來維護三個區(qū)域：小于基準元素的區(qū)域、等于基準元素的區(qū)域和大于基準元素的區(qū)域。在每一次遍歷數(shù)組的過程中，將數(shù)組分為這三個區(qū)域，并將指針移動到合適的位置。最終，數(shù)組會被劃分成小于基準元素、等于基準元素和大于基準元素的三個部分

基本步驟：

數(shù)據(jù)結(jié)構(gòu)排序——詳解快排及其優(yōu)化和冒泡排序(c語言實現(xiàn)、附有圖片與動圖示意）,數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)——排序,數(shù)據(jù)結(jié)構(gòu),算法,c++,java,機器學習,人工智能,c語言

void QuickSort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int begin = left;
	int end = right;

	int mid = GetMid(a, left, right);
	Swap(&a[mid], &a[left]);
	int cur = left + 1;
	int key = a[left];//儲存一下，后面比較來用，用a[left]會被替代
	while (cur <= right)
	{
		if (a[cur] < key)
		{
			Swap(&a[cur], &a[left]);
			cur++;
			left++;
		}
		else if (a[cur] == key)
		{
			cur++;
		}
		else
		{
			Swap(&a[cur], &a[right]);
			right--;
		}
	}
	QuickSort(a, begin, left - 1);
	QuickSort(a, right + 1, end);
}

1.4快排非遞歸

快速排序的非遞歸實現(xiàn)通常使用棧來模擬遞歸調(diào)用的過程。在快速排序的遞歸實現(xiàn)中，每次遞歸調(diào)用都將函數(shù)參數(shù)壓入棧中，然后在遞歸返回時再從棧中彈出參數(shù)(二者性質(zhì)相同)。

非遞歸實現(xiàn)則需要手動維護一個棧，將需要處理的子序列的起始和結(jié)束位置壓入棧中，然后循環(huán)處理棧中的元素，直到棧為空（遞歸一次就用一次）

void QuickSortNonR(int* a, int begin, int end)//利用棧，先想好先排左側(cè)再排右側(cè)
{
	ST st;
	STInit(&st);
	STPush(&st,end);//把各個區(qū)間的兩側(cè)的索引（整形）插入進Stack中
	STPush(&st,begin);//棧（后進先出），先排左側(cè)所以后入左
	while (!STEmpty(&st))
	{
		int left = STTop(&st);
		STPop(&st);
		int right = STTop(&st);
		STPop(&st);

		int keyi = OneSort1(a, left, right);//得到基準元素下標
		// [begin, keyi-1] keyi [keyi+1, end]
		if (keyi + 1 < right)//等于說明就一個，沒必要
		{
			STPush(&st, right);
			STPush(&st, keyi);
		}
		if (left < keyi-1)
		{
			STPush(&st, keyi-1);
			STPush(&st, left);
		}
	}
	STDestroy(&st);
}

2.冒泡排序

它重復地遍歷要排序的列表，比較每對相鄰的元素，并按照大小順序交換它們。重復這個過程直到整個列表排序完成

步驟：

  1. 從列表的第一個元素開始，依次比較相鄰的兩個元素，如果它們的順序不正確就交換它們。
  2. 繼續(xù)遍歷列表，重復上述比較和交換的過程，直到?jīng)]有任何一對相鄰元素需要交換為止。
  3. 列表排序完
void BobbleSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		for (int j = 0; j < n - 1 - i; j++)
		{
			if (a[j] > a[j + 1])
			{
				Swap(&a[j], &a[j + 1]);
			}
		}
	}
}

好啦，這次內(nèi)容就到這里啦，下次帶來歸并排序，感謝大家支持?。?！文章來源地址http://www.zghlxwxcb.cn/news/detail-823921.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)排序——詳解快排及其優(yōu)化和冒泡排序(c語言實現(xiàn)、附有圖片與動圖示意）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！

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

領支付寶紅包贊助服務器費用

相關(guān)文章

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

支付寶掃一掃打賞

博客贊助

微信掃一掃打賞

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

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

二維碼1

領取紅包

二維碼2

領紅包