快捷導(dǎo)航

Java排序算法總結(jié)之選擇排序

更新時(shí)間：2015年05月19日 10:34:01 作者：一羽清寧

這篇文章主要介紹了Java排序算法總結(jié)之選擇排序,較為詳細(xì)的分析了選擇排序的原理與java實(shí)現(xiàn)技巧,需要的朋友可以參考下

本文實(shí)例講述了Java排序算法總結(jié)之選擇排序。分享給大家供大家參考。具體分析如下：

選擇排序的基本操作就是每一趟從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€(gè)元素，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完。算法不穩(wěn)定，O(1)的額外的空間，比較的時(shí)間復(fù)雜度為O(n^2)，交換的時(shí)間復(fù)雜度為O(n)，并不是自適應(yīng)的。在大多數(shù)情況下都不推薦使用。只有在希望減少交換次數(shù)的情況下可以用。

基本思想

n個(gè)記錄的文件的直接選擇排序可經(jīng)過n-1趟直接選擇排序得到有序結(jié)果：
①初始狀態(tài)：無序區(qū)為R[1..n]，有序區(qū)為空。
②第1趟排序
在無序區(qū)R[1..n]中選出關(guān)鍵字最小的記錄R[k]，將它與無序區(qū)的第1個(gè)記錄R[1]交換，使R[1..1]和R[2..n]分別變?yōu)橛涗泜€(gè)數(shù)增加1個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少1個(gè)的新無序區(qū)。
……
③第i趟排序

第i趟排序開始時(shí)，當(dāng)前有序區(qū)和無序區(qū)分別為R[1..i-1]和R(1≤i≤n-1)。該趟排序從當(dāng)前無序區(qū)中選出關(guān)鍵字最小的記錄 R[k]，將它與無序區(qū)的第1個(gè)記錄R交換，使R[1..i]和R分別變?yōu)橛涗泜€(gè)數(shù)增加1個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少1個(gè)的新無序區(qū)。
這樣，n個(gè)記錄的文件的直接選擇排序可經(jīng)過n-1趟直接選擇排序得到有序結(jié)果。

代碼實(shí)現(xiàn)

public class Test { 
  public static int[] a = {10,32,1,9,5,7,12,0,4,3};
  // 預(yù)設(shè)數(shù)據(jù)數(shù)組 
  public static void main(String args[]) { 
    int i; // 循環(huán)計(jì)數(shù)變量 
    int Index = a.length;// 數(shù)據(jù)索引變量 
    System.out.print("排序前: "); 
    for (i = 0; i < Index - 1; i++) 
      System.out.printf("%3s", a); 
    System.out.println(""); 
    SelectSort(Index - 1); // 選擇排序 
    // 排序后結(jié)果 
    System.out.print("排序后: "); 
    for (i = 0; i < Index - 1; i++) 
      System.out.printf("%3s", a); 
    System.out.println(""); 
  } 
  public static void SelectSort(int Index) { 
    int i, j, k; // 循環(huán)計(jì)數(shù)變量 
    int MinValue; // 最小值變量 
    int IndexMin; // 最小值索引變量 
    int Temp; // 暫存變量 
    for (i = 0; i < Index - 1; i++) { 
      MinValue = 32767;// 目前最小數(shù)值 
      IndexMin = 0; // 儲(chǔ)存最小數(shù)值的索引值 
      for (j = i; j < Index; j++) { 
        if (a[j] < MinValue) // 找到最小值 
        { 
          MinValue = a[j]; // 儲(chǔ)存最小值 
          IndexMin = j; 
        } 
        Temp = a; // 交換兩數(shù)值 
        a = a; 
        a = Temp; 
      } 
      System.out.print("排序中: "); 
      for (k = 0; k < Index; k++) 
        System.out.printf("%3s", a[k]); 
      System.out.println(""); 
    } 
  } 
}

選擇排序法與冒泡排序法一樣，最外層循環(huán)仍然要執(zhí)行n-1次，其效率仍然較差。

希望本文所述對大家的java程序設(shè)計(jì)有所幫助。

您可能感興趣的文章: