如何使用java排序，選擇排序java代碼_JAVA簡單選擇排序算法原理及實現

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

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

空間復雜度 O(1)

如何使用java排序？算法改進：每次對比，都是為了將最小的值放到第一位，所以可以一比到底，找出最小值，直接放到第一位，省去無意義的調換移動操作。也可以換一個方向，最后一位與前面每一個比較，每次使最大值沉底，最后一位向前推進。

JAVA源代碼：

public static void selectSort(Date[] days) {

int min;

java常用算法、Date temp;

for (int i = 0; i < days.length; i++) {

min = i;

for (int j = min + 1; j < days.length; j++) {

選擇排序java。if (days[min].compare(days[j]) > 0) {

min = j;

}

}

排序算法比較。if (min != i) {

temp = days[i];

days[i] = days[min];

days[min] = temp;

歸并排序算法、}

}

}

class Date {

java list排序，int year, month, day;

Date(int y, int m, int d) {

year = y;

month = m;

快速排序java、day = d;

}

public int compare(Date date) {

return year > date.year ? 1 : year < date.year ? -1

java冒泡排序？: month > date.month ? 1 : month < date.month ? -1

: day > date.day ? 1 : day < date.day ? -1 : 0;

}

public void print() {

java遞歸、System.out.println(year + " " + month + " " + day);

}

}

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

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

比如對于元素集合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小，但是他們并沒有交換數據)。

以下是簡單選擇排序的一個Java實現版本：

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 個元素 , 構造出相對較小的 (n+1)/2個數，然后再構造出相對較小的[n+1]/4個數，直到只有一個元素為止。構造成一個完全二叉樹。

排序的時候，那個元素就是最小的，取出該最小元素，將該元素替換為"最大值",再調整完全二叉樹。

下面是樹形選擇排序的一個Java實現版：

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){? //如果是右節點

tmp[(j-1)/2] = tmp[j] > tmp[j-1]?tmp[j-1]:tmp[j];

j = (j-1)/2;

}else{? //如果是左節點

tmp[j/2]=tmp[j] > tmp[j+1]? tmp[j+1]:tmp[j];

j = j/2;

}

}

}

}

在構造完全二叉樹的時候對 N 個元素的集合， 需要 2*N -1 個輔助空間。

代碼：

while(j > 0){

if(j%2 == 0){? //如果是右節點

tmp[(j-1)/2] = tmp[j] > tmp[j-1]?tmp[j-1]:tmp[j];

j = (j-1)/2;

}else{? //如果是左節點

tmp[j/2]=tmp[j] > tmp[j+1]? tmp[j+1]:tmp[j];

j = j/2;

}

}

則實現遞歸的構造新集合中的最小值。