Java版選擇排序和插入排序

排序算法不論在c語言，java,.net,php都很重要，冒泡排序、選擇排序、插入排序是用的比較多的。個人覺得冒泡排序比較好理解，無非就是交換位置的過程，如下所示

public class BubbleSort{
public static void main(String[] args){
int score[] = {67, 69, 75, 87, 89, 90, 99, 100};
for (int i = 0; i < score.length -1; i++){ //最多做n-1趟排序
for(int j = 0 ;j < score.length - i - 1; j++){
if(score[j] < score[j + 1]){ //把小的值交換到後面
int temp = score[j];
score[j] = score[j + 1];
score[j + 1] = temp;
}
}
System.out.print("第" + (i + 1) + "次排序結果：");
for(int a = 0; a < score.length; a++){
System.out.print(score[a] + "\t");
}
System.out.println("");
}
System.out.print("最終排序結果：");
for(int a = 0; a < score.length; a++){
System.out.print(score[a] + "\t");
}
}
}

但是像選擇排序和插入排序理解起來會稍微困難一些，這2種排序和冒泡有很大的不同，先來看看插入排序

1.插入排序：

將n個元素的數列分為已有序和無序兩個部分，如下所示：

{{a1}，{a2，a3，a4，…，an}}
{{a1⑴，a2⑴}，{a3⑴，a4⑴ …，an⑴}}
…
{{a1(n-1），a2(n-1) ，…},{an(n-1)}}

每次處理就是將無序數列的第一個元素與有序數列的元素從後往前逐個進行比較，找出插入位置，將該元素插入到有序數列的合適位置中。

這種方式的排序主要就是為待插入的數找合適位置，之後插入變為新數組，在重復同樣的操作，下面是我寫的一段java代碼

package org.lxh;
public class InsertSort {
/**
*插入排序
*/
public static void main(String[] args) {
int arr[]={23,6,45,8,7,24,-2};
for(int i=1;i<arr.length;i++){
//insertVal是准備插入的數
int insertVal=arr[i];
int insertIndex=i-1;
//如果待插入的數小於前一個數，則把較大的數移動到後面
while(insertIndex>=0&&insertVal<arr[insertIndex]){
arr[insertIndex+1]=arr[insertIndex];
//考慮到類似-2這樣的情況，還必須往前面找合適位置
insertIndex--;
}
//到這裡為止我們就為要插入的數據找到了位置
arr[insertIndex+1]=insertVal;

}
for(int k=0;k<arr.length;k++){
System.out.println(arr[k]);
}
}
}

對於這段代碼可能在 insertIndex-- 這個地方理解起來很困難，這裡這樣寫是為了考慮類似-2的這種情況，不是交換一次就可以。