1. 冒泡排序
數組中每一個元素與其後一個元素進行比較，較大的或者較小的放在後面，即其與後面這個元素換位置。即第一個與第二個比，第二個與第三個比，知道倒數第二個與倒數第一個比，之後在數組的末尾就是最大或者最小的數了；之後繼續上一個步驟，不過由于上一趟排序中，最後一個數已經為有序的，是以隻需要比較到倒數第三個與倒數第二個比較；之後比較的次數逐次減少。
java代碼
private void bubbling(int[] arr){
for (int i = 0; i < arr.length - 1; i++){
boolean hasChange = false;
for (int j = 0; j < arr.length - i - 1; j++){
if(arr[j] > arr[j + 1]){
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
hasChange = true;
}
}
if (!hasChange){
break;
}
}
}
效率問題：
慢…
進行80000個數字的排序，效率讓人心碎：
public static void main(String[] args) {
int[] arr = new int[80000];
Random random = new Random();
for (int i = 0; i < arr.length; i++){
arr[i] = random.nextInt(800000);
}
SortDemo sortDemo = new SortDemo();
System.out.println(System.currentTimeMillis());
sortDemo.bubbling(arr);
System.out.println(System.currentTimeMillis());
}
輸出如下：
1585325682398
1585325701677
19秒左右0.0
Go實作
func Bubbling(arr []int){
for i := 0; i < len(arr) - 1; i++ {
count := false
for j := 0; j < len(arr) - i - 1; j++ {
if (arr[j] > arr[j + 1]) {
temp := 0
temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp
count = true
}
}
if(!count){
break;
}
}
}
效率問題：
也是一個慢字…畢竟冒泡 傷不起
80000個數字進行排序
func main(){
arr := make([]int, 80000)
t := time.Now()
fomat := t.UnixNano()
rand.Seed(fomat)
for i := 0; i < len(arr); i++{
arr[i] = rand.Intn(80000)
}
t1 := time.Now()
Bubbling(arr)
t2 := time.Since(t1)
fmt.Println(t2)
}
輸出如下：
15.9531755s
2. 選擇排序
思路：從數組中選出一個最大（最小）值，放入數組頭，或者數組尾，差別在于正向反向，全看自己心情，此處使用正向升序排序。每次找出最小值放入無序端的第一個，即第i個，i從0開始
廢話不多說了，就是選出最小的往前放，上代碼：
java實作
private void choice(int[] arr){
for (int i = 0; i < arr.length - 1; i++){
int min = arr[i];
int minIndex = i;
for (int j = i + 1; j < arr.length; j++){
if (arr[j] < min){
min = arr[j];
minIndex = j;
}
}
if (i != minIndex){
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
效率問題：比起冒泡是好了不少，但時間複雜度還是O(n^2)
依然是那熟悉的80000比資料
public static void main(String[] args) {
int[] arr = new int[80000];
Random random = new Random();
for (int i = 0; i < arr.length; i++){
arr[i] = random.nextInt(800000);
}
SortDemo sortDemo = new SortDemo();
System.out.println(System.currentTimeMillis());
sortDemo.choice(arr);
System.out.println(System.currentTimeMillis());
}
輸出結果：
1585326261907
1585326268503
7秒左右，确實比老爺爺冒泡跑的快了點
Go實作
func choice(arr []int){
for i := 0; i < len(arr) - 1; i++{
min := arr[i]
minIndex := i
for j := i + 1; j < len(arr); j++{
if (arr[j] < min){
min = arr[j]
minIndex = i
}
}
if (i != minIndex){
temp := arr[i]
arr[i] = arr[minIndex]
arr[minIndex] = temp
}
}
}
再以80000比資料跑一遍：
func main(){
arr := make([]int, 80000)
t := time.Now()
fomat := t.UnixNano()
rand.Seed(fomat)
for i := 0; i < len(arr); i++{
arr[i] = rand.Intn(80000)
}
t1 := time.Now()
choice(arr)
t2 := time.Since(t1)
fmt.Println(t2)
}
輸出如下：
6.6854358s
和java兄弟并排走，時間差不多
3. 插入排序
插入排序的思想是，将數組分為兩部分，左邊為有序部分，右邊為無序部分。每次從無序部分取出第一個，與有序部分分别比較，并将其插入到有序部分中，至此，有序部分加一，無序部分減一。當無序部分長度減為0時，整個數組都為有序了
如何插入？
如何了解插入這個命名呢，我們定義
insertIndex
為待被插入的下标，如果我們目前采用的比較的數比
arr[insertIndex]
小（假設是升序排列），那麼将
arr[insertIndex]
向後放，即有如下數組：
[3, 1, 2]
我們選1作為
insertValue
，
insertIndex
為0，那麼此時比較發現
arr[insertIndex] > insertValue
，那麼我們把
3
提起來往後放，放到
arr[insertIndex + 1]
的位置，之後再往前比，發現已經到了最前，就可以将
arr[insertIndex] = insertValue
；隻是舉了一個簡單的例子，如果是：
[2, 3, 4, 5, 1]
我們此時周遊到最後一個元素，即1,此時
insertValue = 1
，
insertIndex = 3
，那麼如下就是該數組的更改順序：
1. [2, 3, 4, 5, 5] insertValue = 1 insertIndex = 3
2. [2, 3, 4, 4, 5] insertValue = 1 insertIndex = 2
3. [2, 3, 3, 4, 5] insertValue = 1 insertIndex = 1
4. [2, 2, 3, 4, 5] insertValue = 1 insertIndex = 0
5. [1, 2, 3, 4, 5] 最後當 insertIndex = 0 時，給 arr[insertIndex] = insertValue
具體分析
int insertValue = arr[1] //需要插入進去的值
Int insertIndex = 1 -1 //将要被插入的元素的前一個元素的下标
while(insertIndex >= 0 && insertValue < arr[insertIndex]){
//上述判斷： 當元素被插入進有序部分後，如果他前面的待被插入元素仍大于等于0， 說明它前面仍然有元素
//當被插入元素的值小于它前面待被插入的元素，說明它現在沒有和目前的前一個元素比較過，
//仍然沒有确定位置，是以需要再進行比較，當它前面沒有元素或者它前面的元素的值小于它，說明它已經正确插入了有序部分
//隻要進入循環，說明它已經執行了一次插入動作，插入的實作為将待插入的元素與前面的元素換位
arr[insertIndex + 1] = arr[insertIndex]
//當換位後，目前待被插入的元素就是目前其所在位置的前一個了，
//因為該元素向前插入了一個位置，是以待被插入的元素位置也向前移動
insertIndex --
}
//因為上述循環中，如果在最後一次循環，插入元素的前面并沒有元素了，或者前一個元素比它小，但是
//insertIndex仍然減一了 是以，待插入的元素的正确位置應該是insertIndex+1
arr[insertIndex + 1] = insertValue
在插入排序中，我們在剛開始時總認為第一個元素自己組成了有序部分，因為也沒有其他元素和他比較大小。是以無序部分的第一個起始為1，之後每次向後加，我們隻需要給這個步驟加一個循環即可；
java實作
private void insertSort(int[] arr){
//循環表示第幾個被插入的數 從1開始
for (int i = 1; i < arr.length; i++){
//需要插入的數為
int insertValue = arr[i];
//待被插入的下标 在待插入數的前一個
int insertIndex = i - 1;
//insertIndex >= 0 當insertIndex小于0時，說明待插入數之前已經沒有資料了，它是最小的數
//insertValue < arr[insertIndex] 當待插入的數小于前一個數時，還不知道它是不是最小，它還需要與它前前一個進行
//比較，但是在此時他已經可以插隊到他前一個數之前
while (insertIndex >= 0 && insertValue < arr[insertIndex]){
// 将目前的位置的數向後移動一位
arr[insertIndex + 1] = arr[insertIndex];
// 将下标值減一，表示将要與目前位置的前一個位置比較
insertIndex--;
}
arr[insertIndex + 1] = insertValue;
}
}
效率分析：
public static void main(String[] args) {
int[] arr = new int[80000];
Random random = new Random();
for (int i = 0; i < arr.length; i++){
arr[i] = random.nextInt(800000);
}
SortDemo sortDemo = new SortDemo();
System.out.println(System.currentTimeMillis());
sortDemo.insertSort(arr);
System.out.println(System.currentTimeMillis());
}
1585326807369
1585326809251
比起選擇排序更快
Go實作
func insertSort(arr []int){
for i := 1; i < len(arr); i++{
insertValue := arr[i]
insertIndex := i - 1
for {
if (insertIndex < 0 || insertValue > arr[insertIndex]){
break
}
arr[insertIndex + 1] = arr[insertIndex]
insertIndex--
}
arr[insertIndex + 1] = insertValue
}
}
執行效率：
func main(){
arr := make([]int, 80000)
t := time.Now()
fomat := t.UnixNano()
rand.Seed(fomat)
for i := 0; i < len(arr); i++{
arr[i] = rand.Intn(80000)
}
t1 := time.Now()
insertSort(arr)
t2 := time.Since(t1)
fmt.Println(t2)
}
執行結果：
1.8607944s
如果走的不快，那就多走幾步。
![Java小案例——随機數猜測随機數猜測[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)