欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C語(yǔ)言常見(jiàn)排序算法之交換排序(冒泡排序,快速排序)

 更新時(shí)間:2022年07月14日 09:38:01   作者:保護(hù)小周?  
這篇文章主要介紹了C語(yǔ)言常見(jiàn)排序算法之交換排序(冒泡排序,快速排序),冒泡排序即Bubble?Sort,類似于水中冒泡,較大的數(shù)沉下去,較小的數(shù)慢慢冒起來(lái),假設(shè)從小到大,即為較大的數(shù)慢慢往后排,較小的數(shù)慢慢往前排

前言

本期為大家?guī)?lái)的是常見(jiàn)排序算法中的交換排序,主要有冒泡排序,快速排序,快排分享了三種算法:挖坑法,左右指針?lè)ǎ昂笾羔樂(lè)?,以及兩種優(yōu)化方式:解決快排最壞情況的“三數(shù)取中”,避免遞歸次數(shù)過(guò)多的"小區(qū)間優(yōu)化",

基本思想:所謂交換,就是根據(jù)序列中兩個(gè)記錄鍵值的比較結(jié)果來(lái)對(duì)換這兩個(gè)記錄在序列中的位 置,交換排序的特點(diǎn)是:將鍵值較大的記錄向序列的尾部移動(dòng),鍵值較小的記錄向序列的前部移 動(dòng)。

1.交換排序——冒泡排序

冒泡排序(Bubble Sort)基本思想: 冒泡排序,類似于水中冒泡,較大的數(shù)沉下去,較小的數(shù)慢慢冒起來(lái),假設(shè)從小到大,即為較大的數(shù)慢慢往后排,較小的數(shù)慢慢往前排。直觀表達(dá),每一趟遍歷,將一個(gè)最大的數(shù)移到序列末尾。也是一種簡(jiǎn)單直觀的排序算法。它重復(fù)地走訪過(guò)要排序的數(shù)列,一次比較兩個(gè)元素,將他們之間小的,或者大的值交換過(guò)來(lái)。遍歷數(shù)列的工作是重復(fù)地進(jìn)行,直到?jīng)]有再需要交換的,也就是說(shuō)該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來(lái)是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢"浮"到數(shù)列的頂端。

1.1 算法思想

比較相鄰的元素,如果前一個(gè)比后一個(gè)大,交換之。
第一趟排序第i個(gè)和第i+1個(gè)比較與交換,隨后第i+1個(gè)和第i+2個(gè)一對(duì)比較交換,這樣直到倒數(shù)第n-1個(gè)和最后n個(gè),將最大的數(shù)移動(dòng)到最后一位。
第二趟將第二大的數(shù)移動(dòng)至倒數(shù)第二位

……

1.2 動(dòng)圖演示

 算法實(shí)現(xiàn):

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define N 10
 
Swap(int *p1, int * p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void Print(int *a)
{
	for (int i=0;i<N;i++)
	{
		printf("%d ",a[i]);
	}
}
void BubbleSort(int* a, int n)
{
	
	for (int j=0;j<n;++j)
	{
		int size = 0;
		for (int i=1;i<N-j;++i)
		{
			if (a[i-1]>a[i])
			{
				Swap(&a[i-1],&a[i]);
				size =1;
			}
		}
		if (size==0)
		{
			break;
		}
	}
}
int main()
{
	int a[N] = {0};
	for (int i=0;i<N;++i)
	{
		a[i] = rand();
	}
	BubbleSort(a,N);
	Print(a);
	
	return 0;
}

其中有一段優(yōu)化程序,是定義一個(gè)變量判斷排序是否在做無(wú)效操作,當(dāng)內(nèi)循環(huán)處于交換狀態(tài)時(shí),則數(shù)據(jù)未排序完畢,否則視為,數(shù)據(jù)已有序,我們就可以break;中止掉程序,避免做無(wú)用遍歷。

1.3 冒泡最好的情況

待排序數(shù)列有序時(shí),時(shí)間復(fù)雜度是O(N)。外循環(huán)只執(zhí)行一次,內(nèi)循環(huán)N-1,N-2,N-3……

冒泡排序的特性總結(jié):

  • 1. 冒泡排序是一種非常容易理解的排序
  • 2. 時(shí)間復(fù)雜度:O(N^2)
  • 3. 空間復(fù)雜度:O(1)
  • 4. 穩(wěn)定
  • 性:穩(wěn)定

總結(jié):

總的來(lái)說(shuō),冒泡排序是一種可以的排序,比直接選擇排序要好,雖然有優(yōu)化程序,但是,整體算法效率跟其他排序來(lái)比,還是差一些,比較適合新手學(xué)習(xí)。

 2. 交換排序——快速排序

快速排序(Quicksort)是Hoare于1962年提出的一種二叉樹結(jié)構(gòu)的交換排序方法,有時(shí)候也叫做劃分交換排序,是一個(gè)高效的算法,其基本思想為:任取待排序 元素序列中的某元素作為基準(zhǔn)值,按照該排序碼將待排序集合分割成兩子序列,左子序列中所有 元素均小于基準(zhǔn)值,右子序列中所有元素均大于基準(zhǔn)值,然后最左右子序列重復(fù)該過(guò)程,直到所 有元素都排列在相應(yīng)位置上為止。這是一個(gè)分治算法,而且它就在原地交換數(shù)據(jù)排序。

是目前已知最快的排序算法,會(huì)比一般的排序更節(jié)省時(shí)間。

2.1 快速排序——挖坑法

算法實(shí)現(xiàn):

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
//打印
void Print(int *a,int n)
{
	for (int i=0;i<n;++i)
	{
		printf("%d ",a[i]);
	}
}
//挖坑法
void QuickSort(int* a,int left,int right)//升序
{
	if (left < right)
	{
		int begin = left;
		int end = right;
		int pivot = begin;//記錄坑位的下標(biāo)
		int key = a[begin];//坑值
 
		while (begin < end)
		{
			//右邊找小,放到左邊
			while (begin < end && a[end] >= key)//與坑值比較
			{
				--end;
			}
			//小的放在左邊的坑里,自己形成了新的坑位
			a[pivot] = a[end];
			pivot = end;
 
			//左邊找大,放在右邊
			while (begin < end && a[begin] <= key)//與坑值比較
			{
				++begin;
			}
			//大的放在右邊的坑里,自己形成了新的坑位
			a[pivot] = a[begin];
			pivot = begin;
		}
		//最后將坑值給到坑位
		a[pivot] = key;
		//[left,right]
		//[left,pivot-1]  [pivot+1,right]
		//左子區(qū)間和右子區(qū)間有序,我們就有序了,如何讓他們有序?分治遞歸
		QuickSort(a, left, pivot - 1);
		QuickSort(a, pivot + 1, right);
	}
	else
	{
		return;
	}
}
int main()
{
	int a[10] = {0,9,5,6,3,2,1,7,8,4};
	//挖坑法
	QuickSort(a,0,sizeof(a)/sizeof(a[0])-1);
    //打印
	Print(a,sizeof(a) / sizeof(a[0]));
	return 0;
}

快排的缺點(diǎn)

根據(jù)上面的代碼,我們來(lái)分析一下快排的缺點(diǎn):

如何解決快排對(duì)有序數(shù)據(jù)排序效率很差的方法?

三數(shù)取中法

所謂三數(shù)取中,不是取最大值,最小值,以及他們的中間值,而是取左邊(begin)、右邊(end)和中間(begin+end)/2;

在有序的情況下中間的值剛好就是二分,將取出的值作為坑位,就不會(huì)出現(xiàn)最差的這種情況。我們依舊使用區(qū)間的開(kāi)頭作為“坑值”,但是要使用三數(shù)取中的邏輯。

選坑位:

int begin = left;
int end = right;
//使用三數(shù)取中選“坑值”,用mid存儲(chǔ)其下標(biāo)
int mid = GetMidIndex(a, begin, end);
//將區(qū)間首值當(dāng)作坑位
//坑值與首值交換,避免算法混亂
//一般我們會(huì)將區(qū)間首值作為坑值
Swap(&a[begin], &a[mid]);//傳地址調(diào)用
//存儲(chǔ)坑值
int key = a[begin];

三數(shù)取中 GetMidIndex();

int GetMidIndex(int *a,int left,int right)
{
    //二分
	int mid = (right - left) / 2;
	if (a[left]<a[mid])
	{
		if (a[left]<a[right])
		{
			if (a[mid]<a[right])
			{
				return mid;
			}
			else  //a[mid]>=a[right]
			{
				return right;
			}
		}
		else   //a[left]>=a[right]
		{
			return left;
		}
	}
	else  //a[left]>=a[mid]
	{
		if (a[mid]<a[right])
		{
			if (a[left]<a[right])
			{
				return left;
			}
			else  //a[left]>=a[right]
			{
				return right;
			}
		}
		else  //a[mid]>=a[right]
		{
			return mid;
		}
	}
}

交換Swap();

//交換
void Swap(int* p1, int*p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

經(jīng)過(guò)三數(shù)取中的處理,就不會(huì)出現(xiàn)快排的最壞情況,但也幾乎不會(huì)成為最好的情況,有利有弊,我們?cè)诿嬖嚨倪^(guò)程中只需要寫基礎(chǔ)版的快排即可,以防時(shí)間不夠。

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

關(guān)于如果處理數(shù)據(jù)多,相應(yīng)的遞歸次數(shù)多,會(huì)不會(huì)影響操作快排的性能?

當(dāng)我們?cè)谑褂每炫艑?duì)大量數(shù)據(jù)進(jìn)行排序時(shí),我們可以采用小區(qū)間優(yōu)化,減少遞歸次數(shù),達(dá)到優(yōu)化程序得到目的。

對(duì)當(dāng)待處理數(shù)據(jù)大于10的子序列進(jìn)行快排遞歸。

對(duì)當(dāng)待處理數(shù)據(jù)低于10的子序列進(jìn)行直接插入排序進(jìn)行排序,避免遞歸次數(shù)過(guò)多。

這個(gè)10不是固定的,可以根據(jù)處理的數(shù)據(jù)量調(diào)整。

//區(qū)間[left,right]
//左區(qū)間[left,pivot-1]  右區(qū)間[pivot+1,right]
//左子區(qū)間和右子區(qū)間有序,我們就有序了,如何讓他們有序?分治遞歸
// 小區(qū)間優(yōu)化
if (pivot - 1 - left > 10)//對(duì)當(dāng)待處理數(shù)據(jù)大于于10的子序列進(jìn)行快排遞歸排序
{
	//快排
	QuickSort(a,left,pivot-1);
}
else
{
	//采用直接插入排序,對(duì)當(dāng)待處理數(shù)據(jù)低于10的子序列進(jìn)行排序,避免遞歸
	InsertSort(a+left,pivot-1-left+1);//為什么最后要加1,例如:區(qū)間[0,9]實(shí)際上有10個(gè)數(shù)
}
 
if (right - (pivot + 1) > 10)
{
	QuickSort(a,pivot+1,right);
}
else
{
	InsertSort(a + pivot+1, right-(pivot+1)+1);
 
}

如果大家有想了解直接插入排序可以查看博主的另一篇:C語(yǔ)言常見(jiàn)排序算法之插入排序(直接插入排序,希爾排序)

2.3 快速排序——左右指針?lè)?/h3>

 根據(jù)上圖的示例我們應(yīng)該能夠理解左右指針?lè)ㄊ鞘裁礃拥倪壿?,跟挖坑法是一樣的思想,單趟排序完畢?shí)現(xiàn)左邊比坑位小,右邊比坑位大。但是即使左右指針?lè)ǜ诳臃ǖ乃枷胧且粯拥?,但是他們單趟的運(yùn)算結(jié)果是不一樣的。

 算法實(shí)現(xiàn):

void QuickSort(int* a, int left, int right)
{
	if (left < right)
	{
		int begin = left;
		int end = right;
		//選坑位
		int mid = GetMidIndex(a, begin, end);//三數(shù)取中
		Swap(&a[begin], &a[mid]);
		int key = begin;
		while (begin < end)
		{
			while (begin < end && a[end] <= a[key])
				--end;
			while (begin < end && a[begin] >= a[key])
				++begin;
			Swap(&a[begin], &a[end]);
		}
		Swap(&a[begin], &a[key]);
		//分治遞歸
		QuickSort(a, left, begin - 1);
		QuickSort(a, begin + 1, right);
	}
}

2.4 前后指針?lè)?/h3>
  • 采用perv記錄區(qū)間第一個(gè)元素的下標(biāo),采用cur記錄區(qū)間第二個(gè)元素的下標(biāo)。
  • cur找小,每次遇到比key(坑值)小的值就停下來(lái),++prev。
  • 交換prev和cur位置的值

 算法實(shí)現(xiàn):

//左右指針?lè)?
void QuickSort(int* a, int left, int right)
{
	if (left < right)
	{
		//選坑位
		int mid = GetMidIndex(a, left,right);//三數(shù)取中
		Swap(&a[left], &a[mid]);
		int key = left;
		//初始化指向
		int prev = left, cur = left + 1;
		while (cur<=right)
		{
			if (a[cur] <= a[key])//&&++prev!=cur
			{
				++prev;
				//避免無(wú)效操作
				if(cur!=prev)
				Swap(&a[prev],&a[cur]);
			}
			++cur;
		}
		Swap(&a[key], &a[prev]);
		//分治遞歸
		QuickSort(a, left, prev - 1);
		QuickSort(a, prev + 1, right);
	}
}

快速排序的特性總結(jié):

  • 1.快速排序整體的綜合性能和使用場(chǎng)景都是比較好的,所以才敢叫快速排序
  • 2.時(shí)間復(fù)雜度:O(N*logN)
  • 3.空間復(fù)雜度:O(logN) 
  • 4.穩(wěn)定性:不穩(wěn)定

總結(jié):

快排是我們一定要掌握的一種排序算法,在面試、筆試中也是很常見(jiàn)的,博主分享的三種方法:挖坑法,左右指針?lè)?,前后指針?lè)?,只少要掌握一種,但是要其他的方法也要知道算法思想。還有兩種優(yōu)化方式,小區(qū)間優(yōu)化和三數(shù)取中,也要知道是什么邏輯,解決什么問(wèn)題。

到此這篇關(guān)于C語(yǔ)言常見(jiàn)排序算法之交換排序(冒泡排序,快速排序)的文章就介紹到這了,更多相關(guān)C語(yǔ)言交換排序 內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • Qt實(shí)現(xiàn)生成指定范圍內(nèi)隨機(jī)數(shù)與隨機(jī)字符串

    Qt實(shí)現(xiàn)生成指定范圍內(nèi)隨機(jī)數(shù)與隨機(jī)字符串

    這篇文章主要為大家詳細(xì)介紹了如何利用Qt實(shí)現(xiàn)生成指定范圍內(nèi)隨機(jī)數(shù)與隨機(jī)字符串,文中的示例代碼簡(jiǎn)潔易懂,感興趣的小伙伴可以自己動(dòng)手嘗試一下
    2023-07-07
  • C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)易文本編輯器

    C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)易文本編輯器

    這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)易文本編輯器,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2021-05-05
  • C++實(shí)現(xiàn)LeetCode(164.求最大間距)

    C++實(shí)現(xiàn)LeetCode(164.求最大間距)

    這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(164.求最大間距),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下
    2021-07-07
  • Linux下C語(yǔ)言實(shí)現(xiàn)C/S模式編程

    Linux下C語(yǔ)言實(shí)現(xiàn)C/S模式編程

    這篇文章主要為大家詳細(xì)介紹了Linux下C語(yǔ)言實(shí)現(xiàn)C/S模式編程的相關(guān)資料,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2016-01-01
  • C語(yǔ)言switch使用之詭異用法詳解

    C語(yǔ)言switch使用之詭異用法詳解

    今天小編就為大家分享一篇C語(yǔ)言switch使用之詭異用法詳解,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧
    2019-12-12
  • 一文帶你深入了解C++中的類型轉(zhuǎn)換

    一文帶你深入了解C++中的類型轉(zhuǎn)換

    在C語(yǔ)言中,如果賦值運(yùn)算符左右兩側(cè)類型不同,或者形參與實(shí)參類型不匹配,或者返回值類型與接收返回值類型不一致時(shí),就需要發(fā)生類型轉(zhuǎn)化。本文主要介紹了C++中常見(jiàn)的四個(gè)類型轉(zhuǎn)換,需要的可以參考一下
    2022-12-12
  • 從匯編看c++中變量類型的深入分析

    從匯編看c++中變量類型的深入分析

    本篇文章是對(duì)c++中的變量類型進(jìn)行了詳細(xì)的分析介紹。需要的朋友參考下
    2013-05-05
  • C++小游戲教程之猜數(shù)游戲的實(shí)現(xiàn)

    C++小游戲教程之猜數(shù)游戲的實(shí)現(xiàn)

    這篇文章主要和大家詳細(xì)介紹如何利用C++做一個(gè)簡(jiǎn)易的猜數(shù)游戲,分為用戶猜數(shù)和系統(tǒng)猜數(shù)。文中的示例代碼講解詳細(xì) ,感興趣的小伙伴可以嘗試一下
    2022-11-11
  • C語(yǔ)言開(kāi)發(fā)實(shí)現(xiàn)掃雷游戲

    C語(yǔ)言開(kāi)發(fā)實(shí)現(xiàn)掃雷游戲

    這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言開(kāi)發(fā)實(shí)現(xiàn)掃雷游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2020-11-11
  • C語(yǔ)言實(shí)現(xiàn)BMP圖像的讀寫功能

    C語(yǔ)言實(shí)現(xiàn)BMP圖像的讀寫功能

    這篇文章主要介紹了C語(yǔ)言實(shí)現(xiàn)BMP圖像的讀寫功能,本文給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2021-04-04

最新評(píng)論