直接選擇排序是選擇排序中最基礎的一部分
在此拿出來講是為了為后面的折半選擇排序和希爾排序(縮小增量排序)做好鋪墊,打好基礎
中心思想:
- 首先有一個需要排序的
array
[ 定義一個變量len = array.length
] - 先認為
array[0]
是一個已經(jīng)排好序的序列饭望,認為array[1]
~array[len-1]
是無序序列拌汇。 - 那么就開始遍歷了斟冕,首先 令
i=1
- 那么將
array[i]
需要插入已經(jīng)有序的序列array[0]
~array[i-1]
中小作。
然后就形成了 有序序列array[0]
~array[i]
- 然后
i++
若i<len
[也就是說數(shù)組沒有out of index 還是存在無序序列的]執(zhí)行步驟4
否則也就是i>=len
的時候就說明所有的無序序列都被插入到了有序的序列中也就是說已經(jīng)排好序列了。
圖的例子:
說了那么多還是上個圖比較實在瘦麸,圖的排序過程很形象鸽扁。
直接選擇排序.png
代碼實現(xiàn):
根據(jù)看了一些博客啥的蒜绽,發(fā)現(xiàn)直接排序?qū)崿F(xiàn)方案有幾種,在此將自己了解到的列出來桶现。
1. my-version
package directInsertion;
import java.util.Arrays;
/**
* 直接插入排序 默認的排序規(guī)則為從小到大的排序方式
*
* @author mengf
*
*/
public class Main {
public static int[] directInsertionSort(int[] array) {
for (int i = 1; i < array.length; i++) {
// 判斷array[i]需要放入的array的正確位置 j記錄正確位置的index
int j = i - 1;
for (; j >= 0; j--) {
// 一旦比前面某個大就說明在那個后面一個
if (array[j] <= array[i]) {
j++;
break;
}
// array[i]應該在0位置的情況
if (j == 0) {
break;
}
}
int temp = array[i];
// 找到array[i]對應的位置之后就需要插入
for (int k = i; k > j; k--) {
array[k] = array[k - 1];
}
array[j] = temp;
}
return array;
}
public static void main(String[] args) {
int[] array = { 5, 9, 6, 2 };
directInsertionSort(array);
System.out.println(Arrays.toString(array));
}
}
說實在的我個人能力有限躲雅,弄成這樣我就滿意了,但是之后發(fā)現(xiàn)網(wǎng)上有更簡潔的代碼骡和,一比較才發(fā)現(xiàn)自己是多么的麻煩
發(fā)上一個簡單版本:
2. simple version
這是一個邊移動 邊比較的方法 相當于my-version將內(nèi)循環(huán)中的兩個for糅合
my-version 是先比較完確定好位置之后 再移動
package directInsertion;
import java.util.Arrays;
/**
* 直接插入排序 默認的排序規(guī)則為從小到大的排序方式
*
* @author mengf
*
*/
public class Main {
public static int[] directInsertionSort(int[] array) {
for (int i = 1; i < array.length; i++) {
// 只有i比前面一個排好序的小的時候才說明需要前移 否則說明不需要前移
if (array[i] < array[i - 1]) {
int temp = array[i];
// //邊比較邊移動
// for (int j = i - 1; j >= 0; j--) {
// if (array[j] > temp) {
// array[j + 1] = array[j];
// if (j == 0) {
// array[j] = temp;
// }
// } else {
// array[j + 1] = temp;
// break;
// }
// }
//這樣寫可以不像上面那樣 把j=0 挑出來 防止數(shù)組邊界溢出
//想想很有道理O嗔蕖O嗫堋!钮科!
int j = i - 1;
for (; j >= 0 && array[j] > temp; j--) {
array[j+1] = array[j];
}
array[j+1] = temp;
}
}
return array;
}
public static void main(String[] args) {
int[] array = { 5, 9, 6, 2 };
directInsertionSort(array);
System.out.println(Arrays.toString(array));
}
}