詳解Java之冒泡排序與選擇排序

更新時間：2022年01月10日 09:04:30 作者：小夏跑不死

這篇文章主要為大家介紹了Java之冒泡排序與選擇排序，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助

一.冒泡排序

1.概念

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

2.圖解

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

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

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

3.代碼的思路

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

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

這個代碼也用了兩次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]序列的數(shù)字，然后冒泡循環(huán)進行排序來實現(xiàn)

#include<stdio.h>
int main()
{
	int a[10], i, j, b, k;
	for (i = 0; i < 10;i++)
	{
		printf("輸入第%d個數(shù)為：", i+1);
		scanf_s("%d", &a[i]);
   }
	for (k = 0; k < 9; k++)//外部循環(huán)
	   		for (i = 0; i < 9 - k; i++)//內(nè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)的主要是選擇，選擇一個元素去進行比較，假如這個數(shù)比他小，換成嘞個數(shù)繼續(xù)比較，最后找出最小值與數(shù)組第一位的數(shù)進行交換。然后一直這樣循環(huán)下去，直到代碼排序完成。也就是通過一個中間量從帶排序的的數(shù)中找出最大或最小的交換到對應位置。

2.圖解

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

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

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

3.代碼的思路

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

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

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

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