一、排序分類

簡單寫下如下4種排序：

二、排序介紹

2.1 冒泡排序

思路：比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。每輪冒泡出一個(gè)最大或者最小元素出來。

public static int[] bubbleSort(int[] arr) {
   for (int i = 0; i < arr.length; i++) {
       for (int j = i + 1; j < arr.length; j++) {
           if (arr[i] > arr[j]) {
               int tmp = arr[i];
               arr[i] = arr[j];
               arr[j] = tmp;
           }
       }
   }
   return arr;
}

冒泡排序

2.2選擇排序

思路：第一輪找到最小元素，與0號(hào)元素互換，第二輪找到第二小元素與1號(hào)元素互換，以此類推

public static int[] selectSort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        int min = i;
       for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[min]) {
                min = j;
           }
        }
        if (min != i) {
            int tmp = arr[i];
           arr[i] = arr[min];
           arr[min] = tmp;
       }
    }
    return arr;
}

選擇排序

2.3 插入排序

思路：遍歷數(shù)組，后面的每一位都與前面已排序的數(shù)組進(jìn)行掃描比較，確定對(duì)應(yīng)的順序位置并插入，其余元素均往后移1位。

public static int[] insertSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int cur = arr[i];
        int j;
        for (j = i-1; j >= 0; j--) { //與之前的每一個(gè)數(shù)比較
           if(cur < arr[j]){
               arr[j+1] = arr[j];//比較之后立即移動(dòng)位置
           }else {
               break;
           }
        }
        //插入屬于到對(duì)應(yīng)位置（這里因?yàn)樽隽薺--，所以需要+1加回來）
        arr[j+1] = cur;
    }
    return arr;
}

插入排序

2.4 快速排序

思路：分治 + 遞歸
先從數(shù)列中取出一個(gè)數(shù)作為key值，左右兩邊指針往中間走，左邊找出比基準(zhǔn)大的數(shù)，右邊找出比基準(zhǔn)小的數(shù)，兩者交換。如果左右指針相交，則該位置值與基準(zhǔn)位置交換值。然后再依次遞歸當(dāng)前基準(zhǔn)位置的左邊部分和右邊部分。最終每個(gè)小數(shù)列有序，拼成一整個(gè)有序數(shù)列。

    public static void quickSort(int[] arr, int low, int high) {
        if (low > high) {
            return;
        }
        int i = low;
        int j = high;
        int key = arr[low];

        while (i < j) {
            while (key <= arr[j] && i < j) {
                j--;
            }

            while (key >= arr[i] && i < j) {
                i++;
            }

            if (i < j) {
                int tmp = arr[j];
                arr[j] = arr[i];
                arr[i] = tmp;
            }
        }

        //最后將基準(zhǔn)位置與i和j重疊的位置交換
        arr[low] = arr[i];
        arr[i] = key;

        //遞歸調(diào)用左半邊數(shù)組
        quickSort(arr, low, j - 1);
        //遞歸調(diào)用右半邊數(shù)組
        quickSort(arr, j + 1, high);
    }

快速排序

未完待續(xù)...

動(dòng)圖出處：
http://www.itdecent.cn/p/c4217456c224