C++冒泡排序與選擇排序詳解

更新時間：2021年12月24日 08:42:02 作者：小夏跑不死

大家好，本篇文章主要講的是C++冒泡排序與選擇排序詳解，感興趣的同學趕快來看一看吧，對你有幫助的話記得收藏一下，方便下次瀏覽

?一.冒泡排序

1.概念

冒泡排序這種排序方法其實關鍵詞就在于冒泡兩個字，顧名思義就是數字不斷比較然后最大的突出來，也就是說把相鄰的兩個數字兩兩比較，當一個數字大于右側相鄰的數字時，交換他們的位置，當一個數字和他右側的數字小于或等于的時候，不交換。

?2.圖解

關于冒泡排序我自己畫了一幅圖來描述他的一輪過程

這里我舉了五個無序的數{7,3,6,5,4}

?由此可看出他不斷與右側相鄰的數字進行比較，當他大于右邊的數字就交換，否則不交換，就用這種方法不斷進行排序進行很多輪，最后得出一個有序的序列{2,4,5,6,7}。

3.代碼的思路

冒泡循環(huán)是一種有序的序列，有上圖我們不難看出冒泡循環(huán)一輪需要進n-1次比較然后開啟下一層，而且你一輪比較完了之后最后一個最大的數就不用再參與比較循環(huán)了，所以下一次的循環(huán)可以減少一次。

因此我的思路是利用兩次for循環(huán)，一次循環(huán)來當取第二次循環(huán)的次數，然后依次減少第二次for循環(huán)的次數，簡便了很多過程，然后數組兩個相鄰的數字進行依次比較，大于右邊的也就是大于下一位的交換位置，否則不交換，所以我的兩個for循環(huán)的代碼如下（其實這也算是個萬能代碼，就冒泡循環(huán)這一塊）當然i,k,b都需要來定義的，n為比較序列中元素個數。

這個代碼也用了兩次for循環(huán)所以我們不難推算出時間復雜度為o(n^2)

for(i=0;i<n-1;i++)
{ 
 for(k=0;k<n-1-i;k++)
   { if(a[k]>a[k+1])
     { b=a[k];
       a[k]=a[k+1];
       a[k+1]=b; 
      }//交換a[k]與a[k+1]位置            
     }
 }

4.代碼例子

我自己也寫了一個代碼，輸入a[10]序列的數字，然后冒泡循環(huán)進行排序來實現

#include<stdio.h>
int main()
{
	int a[10], i, j, b, k;
	for (i = 0; i < 10;i++)
	{
		printf("輸入第%d個數為：", i+1);
		scanf_s("%d", &a[i]);
   }
	for (k = 0; k < 9; k++)//外部循環(huán)
	   		for (i = 0; i < 9 - k; i++)//內部循環(huán)
			if(a[i] > a[i + 1])//
			{
				b = a[i];
				a[i]= a[i + 1];
				a[i + 1] = b;
			}
		
	printf("排出序列為：");
	for(i = 0; i < 10; i++)
		printf("%d ", a[i]);
	return 0;
}

最后運行也是成功的

?二.選擇排序

1.概念

選擇循環(huán)的主要是選擇，選擇一個元素去進行比較，假如這個數比他小，換成嘞個數繼續(xù)比較，最后找出最小值與數組第一位的數進行交換。然后一直這樣循環(huán)下去，直到代碼排序完成。也就是通過一個中間量從帶排序的的數中找出最大或最小的交換到對應位置。

2.圖解

關于選擇排序我自己花了一幅圖來描述他的一輪比較

我用了五個無序數來做例子{2,1,4，-3,3}

?由此可以看出選擇比較的過程，這里我用指針代指了需要的中間量，剛開始指針指向2，然后2去比較，1<2，所以指針指向較小值，指針指向1，最后就這樣找出-3為最小值和第一個交換，得到第一輪循環(huán)比較的數列{-3,1,4,2,3}。

3.代碼的思路

其實觀察上圖一輪循環(huán)次數還有循環(huán)完一輪之后，不需要用最小值比較可以看出其實他和冒泡循環(huán)有點相似，都是循環(huán)一輪需要進n-1次比較然后開啟下一層，而且下一次循環(huán)可以減少一次。

所以我的思路是，依然運用兩次for循環(huán)，與冒泡循環(huán)不同的是我需要一個中間商，所以我可以引用一個局部變量來幫助我，這個局部變量就是圖解的指針，局部變量就是數組對應元素的位置，不斷進行比較，當他小于一個數時，他就等于嘞個數的位置數，繼續(xù)比較，直到循環(huán)結束找出最小值，最小值跟第一位換位置，一次循環(huán)直到排出有序序列為止。所以代碼如下

for(i=o;i<n-1:i++）//循環(huán)數列取得數開始依次比較
{ 
  int x=i;//x為中間商
  for(k=i+1;k<n;k++)//從循環(huán)數列取得數后一位開始循環(huán)數列取得數進行依次比較
    {
      if(a[x]>a[k])//得出最小值
        k=x;
        if(x!=i)//將得到的最小值跟最前面的數字進行交換
        { t=a[i];
          a[i]=a[x];
          a[x]=t;
        }
     }
 }

這也是一個萬能代碼可以用在選擇序列上。