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

JAVA簡單選擇排序算法原理及實現(xiàn)

 更新時間:2014年01月19日 13:27:41   作者:  
選擇排序(Selection Sort )分為兩種 簡單選擇排序(Simple Selection Sort) 和樹形選擇排序

簡單選擇排序:(選出最小值,放在第一位,然后第一位向后推移,如此循環(huán))第一位與后面每一個逐個比較,每次都使最小的置頂,第一位向后推進(即剛選定的第一位是最小值,不再參與比較,比較次數(shù)減1)

復雜度: 所需進行記錄移動的操作次數(shù)較少 0--3(n-1) ,無論記錄的初始排列如何,所需的關鍵字間的比較次數(shù)相同,均為n(n-1)/2,總的時間復雜度為O(n2);
空間復雜度 O(1)

算法改進:每次對比,都是為了將最小的值放到第一位,所以可以一比到底,找出最小值,直接放到第一位,省去無意義的調(diào)換移動操作。也可以換一個方向,最后一位與前面每一個比較,每次使最大值沉底,最后一位向前推進。

JAVA源代碼:

復制代碼 代碼如下:

 public static void selectSort(Date[] days) {
  int min;
  Date temp;
  for (int i = 0; i < days.length; i++) {
   min = i;
   for (int j = min + 1; j < days.length; j++) {
    if (days[min].compare(days[j]) > 0) {
     min = j;
    }
   }
   if (min != i) {
    temp = days[i];
    days[i] = days[min];
    days[min] = temp;
   }
  }
 }
class Date {
 int year, month, day;

 Date(int y, int m, int d) {
  year = y;
  month = m;
  day = d;
 }

 public int compare(Date date) {
  return year > date.year ? 1 : year < date.year ? -1
    : month > date.month ? 1 : month < date.month ? -1
      : day > date.day ? 1 : day < date.day ? -1 : 0;
 }

 public void print() {
  System.out.println(year + " " + month + " " + day);
 }
}


  簡單選擇排序(Simple Selection Sort):

  簡單選擇排序類似于冒泡排序(Bubble Sort) ,每次都會在剩下的元素集合中選擇出一個最值出來填充到當前位置。唯一的區(qū)別是,冒泡排序在每次發(fā)現(xiàn)比當前值小于(或大于)時,都會交換元素的位置, 而 簡單選擇排序是選擇剩余元素中的最值和當前位置交換數(shù)據(jù)。

  比如對于元素集合R={37, 40, 38, 42, 461, 5,  7, 9, 12}

  在第一趟排序中:37直接和5交換, 形成新的序列 R1={5,40,38,42,461,37,7,9,12}
  在第二趟排序中:40直接和7交換, 形成新的序列 R2={5,7,38,42,461,37,40,9,12}

  以此類推,直到最后一個元素(注意:在第二趟排序中,38比42小,但是他們并沒有交換數(shù)據(jù))。

  以下是簡單選擇排序的一個Java實現(xiàn)版本:

復制代碼 代碼如下:

  public static void selectionSort(int[] data) {
  if (data == null || data.length <= 1)
  return;
  int i, j, value, minPos, len = data.length;
  int outer = len - 1, tmp;
  for (i = 0; i < outer; i++) {
  value = data[i];
  minPos = -1;
  for (j = i + 1; j < len; j++) {
  if (data[j] < value) {
  minPos = j;
  value = data[j];
  }
  }
  if (minPos != -1) {
  tmp = data[i];
  data[i] = value;
  data[minPos] = tmp;
  }
  //            for (int k = 0; k < len; k++) {
  //                System.out.print(data[k] + " , ");
  //            }
  //            System.out.println();
  }
  }
  public static void main(String[] args) {
  int[] coll = {
  37, 40, 38, 42, 461, 5,  7, 9, 12
  };
  selectionSort(coll);
  for (int i = 0; i < coll.length; i++) {
  System.out.print(coll[i] + " , ");
  }
  }

  樹選擇排序(Tree Selection Sort)
  樹選擇排序算法相對于簡單選擇排序來說是典型的以空間換時間的算法。其思想是對待排序的 N 個元素 , 構(gòu)造出相對較小的 (n+1)/2個數(shù),然后再構(gòu)造出相對較小的[n+1]/4個數(shù),直到只有一個元素為止。構(gòu)造成一個完全二叉樹。
  排序的時候,那個元素就是最小的,取出該最小元素,將該元素替換為"最大值",再調(diào)整完全二叉樹。
下面是樹形選擇排序的一個Java實現(xiàn)版:

復制代碼 代碼如下:

  public static void treeSelectionSort(int[] data) {
  if (data == null || data.length <= 1)
  return;
  int len = data.length , low = 0 , i , j;
  // add Auxiliary Space
  int[] tmp = new int[2*len -1];
  int tSize = tmp.length;
  //construct a tree
  for(i =len-1 , j=tmp.length-1;i >=0 ;i--,j--){
  tmp[j]=data[i];
  }
  for(i = tSize -1 ; i > 0 ; i-=2){
  tmp[(i-1)/2] = tmp[i] > tmp[i-1]? tmp[i-1]:tmp[i];
  }
  //end
  //remove the minimum node.
  while(low < len){
  data[low++] = tmp[0];
  for(j=tSize-1;tmp[j]!=tmp[0];j--);
  tmp[j] = Integer.MAX_VALUE;
  while(j > 0){
  if(j%2 == 0){  //如果是右節(jié)點
  tmp[(j-1)/2] = tmp[j] > tmp[j-1]?tmp[j-1]:tmp[j];
  j = (j-1)/2;
  }else{  //如果是左節(jié)點
  tmp[j/2]=tmp[j] > tmp[j+1]? tmp[j+1]:tmp[j];
  j = j/2;
  }
  }
  }
  }

  在構(gòu)造完全二叉樹的時候?qū)?N 個元素的集合, 需要 2*N -1 個輔助空間。
  代碼:

復制代碼 代碼如下:

  while(j > 0){
  if(j%2 == 0){  //如果是右節(jié)點
  tmp[(j-1)/2] = tmp[j] > tmp[j-1]?tmp[j-1]:tmp[j];
  j = (j-1)/2;
  }else{  //如果是左節(jié)點
  tmp[j/2]=tmp[j] > tmp[j+1]? tmp[j+1]:tmp[j];
  j = j/2;
  }
  }

  則實現(xiàn)遞歸的構(gòu)造新集合中的最小值。

相關文章

  • Java中Date和LocalDate區(qū)別與介紹

    Java中Date和LocalDate區(qū)別與介紹

    本文主要介紹了Java中Date和LocalDate區(qū)別與介紹,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2023-07-07
  • Java字符拼接成字符串的注意點詳解

    Java字符拼接成字符串的注意點詳解

    這篇文章主要介紹了Java字符拼接成字符串的注意點詳解,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
    2019-07-07
  • Spring Security和自定義filter的沖突導致多執(zhí)行的解決方案

    Spring Security和自定義filter的沖突導致多執(zhí)行的解決方案

    這篇文章主要介紹了Spring Security和自定義filter的沖突導致多執(zhí)行的解決方案,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2021-06-06
  • java中的this引用及對象構(gòu)造初始化

    java中的this引用及對象構(gòu)造初始化

    這篇文章主要介紹了java中的this引用及對象構(gòu)造初始化,文章圍繞主題展開詳細的內(nèi)容介紹,具有一定的參考價值,需要的小伙伴可以參考一下
    2022-08-08
  • Java中的Phaser并發(fā)階段器詳解

    Java中的Phaser并發(fā)階段器詳解

    這篇文章主要介紹了Java中的Phaser并發(fā)階段器詳解,Phaser由JDK1.7提出,是一個復雜強大的同步輔助類,是對同步工具類CountDownLatch和CyclicBarrier的綜合升級,能夠支持分階段實現(xiàn)等待的業(yè)務場景,需要的朋友可以參考下
    2023-12-12
  • 基于Java利用static實現(xiàn)單例模式

    基于Java利用static實現(xiàn)單例模式

    這篇文章主要介紹了基于Java利用static實現(xiàn)單例模式,當在多個線程同時觸發(fā)類的初始化過程的時候static不會被多次執(zhí)行,下面我們一起進入文章看看具體要的原因
    2022-01-01
  • Spring中的Bean對象初始化詳解

    Spring中的Bean對象初始化詳解

    這篇文章主要介紹了Spring中的Bean對象初始化詳解,我們也可以根據(jù)Java語言的特性猜測到其很有可能是通過反射機制來完成Bean的初始化操作,接下來我們一步一步的剖析Spring對Bean的初始化操作,需要的朋友可以參考下
    2023-12-12
  • Java中int和Integer的區(qū)別

    Java中int和Integer的區(qū)別

    這篇文章主要介紹的是?Java中int和Integer的區(qū)別,Java?是一種強數(shù)據(jù)類型的語言,因此所有的屬性必須有一個數(shù)據(jù)類型,下面文章基于Java詳細int和Integer有何區(qū)別,需要的朋友可以參考一下
    2021-11-11
  • java實現(xiàn)抽獎概率類

    java實現(xiàn)抽獎概率類

    這篇文章主要為大家詳細介紹了java實現(xiàn)抽獎概率類,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2020-11-11
  • Java中的collection集合類型總結(jié)

    Java中的collection集合類型總結(jié)

    Java的集合類型都是對java.util包中Collection接口的繼承,這里我們主要介紹依賴于collection的一些主分支,一起來看一下Java中的collection集合類型總結(jié)
    2016-05-05

最新評論