摘要：常見(jiàn)排序算法及其實(shí)現(xiàn)說(shuō)明如果有幸能看到本文中的代碼是參考編程思想某培訓(xùn)機(jī)構(gòu)。若兩個(gè)記錄和的關(guān)鍵字相等，但排序后的先后次序保持不變，則稱(chēng)為這種排序算法是穩(wěn)定的。

如果有幸能看到

1、本文中的代碼是參考《Java編程思想》、某培訓(xùn)機(jī)構(gòu)。

2、文中的代碼放Github了，有興趣的可以看看，點(diǎn)個(gè)star鼓勵(lì)下我。

3、代碼在Sublime中敲的，坑爹的GBK，注釋了很多中文，一轉(zhuǎn)碼不能用了！！！

4、重點(diǎn)在思想，而不是實(shí)現(xiàn) 。再次推薦《Java編程思想》

5、如有拼寫(xiě)錯(cuò)誤，還請(qǐng)諒解。本文只為自己復(fù)習(xí)使用，最后放了兩個(gè)收藏非常有水準(zhǔn)的文章鏈接。

排序：假設(shè)含有n個(gè)記錄的序列{R1,R2,R3..,Rn}，其中的關(guān)鍵字序列為{K1,K2,K3...,Kn}。將這些記錄重新排序?yàn)閧Ri1,Ri2,Ri3,Rin} ,使得相應(yīng)的關(guān)鍵字滿(mǎn)足Ki1<=Ki2<=..<=Kim,這樣的一種操作被稱(chēng)為排序。

通常來(lái)說(shuō)，排序的目的是快速查找

衡量排序算法的優(yōu)勢(shì)：

1、時(shí)間復(fù)雜度：分析關(guān)鍵字的比較次數(shù)和記錄的移動(dòng)次數(shù)。

2、空間復(fù)雜度：分析排序算法中需要多少輔助內(nèi)存。

3、若兩個(gè)記錄A和B的關(guān)鍵字相等，但排序后A、B、的先后次序保持不變，則稱(chēng)為這種排序算法是穩(wěn)定的。

排序算法分類(lèi)：內(nèi)部排序和外部排序

內(nèi)部排序：整個(gè)排序過(guò)程不需要借助于外部存儲(chǔ)器(如此攀等)，整個(gè)排序在內(nèi)存中完成。

外部排序：參與排序的數(shù)據(jù)非常多，數(shù)據(jù)量非常大，計(jì)算機(jī)無(wú)法把整個(gè)排序過(guò)程放在內(nèi)存中完成，必須借助于外部存儲(chǔ)器，外部排序最常見(jiàn)的是多路歸并排序，可以認(rèn)為外部排序由多次內(nèi)部所組成。

常用的內(nèi)部排序

選擇排序

直接選擇排序

堆排序

交換排序

冒泡排序

快速排序

插入排序

直接插入、折半插入

歸并排序

桶式排序

基數(shù)排序

基本原理：
將待排序的元素分為已排序和未排序，依次將為排序的元素中最小的元素放入已排序的組中，

直接排序簡(jiǎn)單直觀，但性能略差：堆排序是一種較為搞笑的選擇排序。但實(shí)現(xiàn)起來(lái)略為復(fù)雜。

代碼實(shí)現(xiàn)：

import java.util.Arrays.*;
//選擇排序,
public class SelectSort{
    public static void selectSort(int[] data) {

        int arrayLength = data.length;
        for (int i = 0; i < arrayLength - 1 ; i++ ) {
            for (int j= i +1; j < arrayLength; j++ ) {
                if (data[i] > data[j]) {
                    swap(data,i,j);
                }
            }
        }
        System.out.println("排序后 " + java.util.Arrays.toString(data));


    }

  //第一種通過(guò)臨時(shí)變量來(lái)完成交換
  //注意這里可以用另外一中一種方式
    static void swap(int[] data,int i,int j) {
            int tmp = data[i];
            data[i] = data[j];
            data[j] = tmp;
        }


    public static void main(String[] args) {
        int[] data = {3,4,2,6,8,1,9};
        selectSort(data);
    }
}

改進(jìn)版的選擇排序：

//選擇排序算法
//選擇排序算法
//1、主要思想就是每次假設(shè)一個(gè)最小的值
public class SelectSort1 {
    public static void selectSort1(int[] data) {
        int arraylength = data.length;
        for (int i = 0; i < arraylength - 1; i++ ) {
            int minIndex = i;      //每次假設(shè)一個(gè)最小值下標(biāo)
            for (int j = i + 1; j < arraylength ; j++ ) {
                if (data[minIndex] > data[j]) {
                minIndex = j;
                }
            }
            //判斷需要交換的下標(biāo)是否為自己
            if (minIndex != i) {
                 data[minIndex] = data[minIndex] + data[i];
                 date[i] = date[minIndex] - data[i];
                 data[minIndex] = data[minIndex] - data[i];
            }

        }
        //輸出結(jié)果
        for (int d :data ) {
            System.out.println("排序之后：" + d);
        }
    }

    public static void main(String[] args) {
        int[] data = {3,4,2,6,8,1,9};
        selectSort1(data);
    }
}

直接選擇排序效率分析

算法的時(shí)間效率：無(wú)論初始化狀態(tài)如何，在第i趟排序中選擇最小的元素，需要n-1次比較

算法的空間效率：空間效率較高，只需要一個(gè)附加程序單元用于交換，其空間效率為O(1)

算法的穩(wěn)定性：不穩(wěn)定

資料和代碼來(lái)自這家，有一種感覺(jué)，年代越遠(yuǎn)，越重視基礎(chǔ)。現(xiàn)在的培訓(xùn)呢？

堆排序就是把最大堆堆頂?shù)淖畲髷?shù)取出，將剩余的堆繼續(xù)調(diào)整為最大堆，再次將堆頂?shù)淖畲髷?shù)取出，這個(gè)過(guò)程持續(xù)到剩余數(shù)只有一個(gè)時(shí)結(jié)束

最大堆調(diào)整（Max-Heapify）：將堆的末端子節(jié)點(diǎn)作調(diào)整，使得子節(jié)點(diǎn)永遠(yuǎn)小于父節(jié)點(diǎn)

創(chuàng)建最大堆（Build-Max-Heap）：將堆所有數(shù)據(jù)重新排序，使其成為最大堆

堆排序（Heap-Sort）：移除位在第一個(gè)數(shù)據(jù)的根節(jié)點(diǎn)，并做最大堆調(diào)整的遞歸運(yùn)算

這個(gè)有點(diǎn)難啊，下一個(gè)。回來(lái)再來(lái)看。

相鄰兩元素進(jìn)行比較，如有需要?jiǎng)t進(jìn)行交換，每完成一次循環(huán)就將最大元素排在前面(從小到大排序)下一次循環(huán)是將其他的數(shù)進(jìn)行類(lèi)似的比較。

代碼實(shí)現(xiàn)：

//冒泡排序
public class BubbleSort {
    static void sort(int[] data) {
        int len = data.length;
        for (int i = 0; i < len - 1; i++ ) {
            for (int j = 0 ; j < len - 1 - i; j++ ) {
                if (data[j] > data[j + 1]) {
                    swap(data,j,j+1);
                }
            }
        }

    }
    static void swap(int[] data,int i,int j) {
        int tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
    }

    public static void main(String[] args) {
        int[] data = {4,2,6,8,2,1,0};
        sort(data);
        for(int d : data) {
            System.out.print("->" + d);
        }
    }
}

冒泡排序效率分析：

算法的時(shí)間效率：從冒泡排序的算法可以看出，若待排序的元素為正序，則只需進(jìn)行一趟排序，比較次數(shù)為n-1次，移動(dòng)元素次數(shù)為0；若待排序的元素為逆序，則需要進(jìn)行n-1趟排序.

算法的空間效率：空間效率很高，只需要一個(gè)附加程序單元用于交換，其空間效率為O(1)

算法的穩(wěn)定性：穩(wěn)定

快速排序(Quick Sorting)基本思想是：任取待排序序列中的某個(gè)元素為界點(diǎn)，通過(guò)一次劃分，將待排序元素分為左右兩個(gè)子序列，左子序列元素的排列序列均小于界點(diǎn)元素的排序碼，右子序列的排序碼則大于或等于界點(diǎn)的排序碼，然后分別對(duì)兩個(gè)字序列繼續(xù)進(jìn)行劃分，直至每一個(gè)序列只有一個(gè)元素為止。

一定要認(rèn)真啊，認(rèn)真啊，認(rèn)真啊！！！
代碼實(shí)現(xiàn)：

//快速排序
public class QuickSort {
    private static void swap(int[] data,int i,int j) {
        int tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
    }

    private static void subSort(int[] data,int start,int end) {
        if (start < end) {
         int base = data[end];

         int i = start;
         int j = end + 1;

         while(true) {
             while(i < end && data[++i] <= base) ;
             while(j > start && data[--j] >= base);
             if (i > j) {
                 swap(data,i,j);
             }else {
                 break;
            }
        }

            swap(data, start, j);
            subSort(data, start, j - 1);
            subSort(data, j + 1, end);
        }

    }
    public static void quickSort(int[] data) {
        subSort(data,0,data.length - 1);
    }

    public static void main(String[] args) {
        int[] data = {9,5,6,88};
        quickSort(data);
        System.out.print(java.util.Arrays.toString(data));
    }
}

基本思想：每次將一個(gè)待排序的元素，按其關(guān)鍵字的大小插入到前面已經(jīng)排好序的子序的合適位置，直到全部記錄插入完成。

* 插入算法.
* 1,從后向前找到合適的位置插入
* 基本思想：每步將一個(gè)待排序的記錄，按其順序碼大小插入到前面已經(jīng)排好的子序列的合適位置
* 直到全部插入為止
*/
public class InsertSort {
   public static void main(String[] args) {
       //待排序的數(shù)列
       int[] nums = {43, 23, 64, 24, 34, 78, 32};
       //控制比較的輪數(shù)
       for (int i = 1; i < nums.length; i++) {
           //記錄操作數(shù)
           int temp = nums[i];
           int j = 0;
           for (j = i - 1; j >= 0; j--) {
               //后一個(gè)和前一個(gè)比較，如果前面的大，則把前面的賦值到后面。
               if (nums[j] > temp) {
                   nums[j+1] = nums[j];
               } else {
                   break;
               }
           }
           if (nums[j + 1] != temp) {
               nums[j + 1] = temp;
           }
       }
       //輸出結(jié)果
       for(int n : nums) {
           System.out.println(n);
       }
   }
}

直接插入排序：

直接插入排序 的基本思想：把n個(gè)待排序的元素堪稱(chēng)為一個(gè)有序表和無(wú)序表，開(kāi)始時(shí)有序表中只包含一個(gè)元素，無(wú)序表中有n-1個(gè)元素，排序過(guò)程中每次從無(wú)序表中取出第一個(gè)元素的排序碼進(jìn)行比較，將它插入到有序表中的適當(dāng)位置，使之成為新的有序表。

代碼實(shí)現(xiàn)：

//直接插入排序
public class InsertSort {
    public static void insertSort(int[] data) {
        int arrayLength = data.length;
        for (int i = 1; i < arrayLength; i++) {
            int tmp = data[i];

            if (data[i] < data[i -1]) {
                int j = i - 1;
                for (;j >=0 && data[j] > tmp; j-- ) {
                    data[j + 1] = data[j];
                }
                data[j + 1] = tmp;
            }

        }
    }
    public static void main(String[] args) {
        int[] data = {5,2,6,9};
        insertSort(data);
        for (int d :data ) {
            System.out.print(" " + d);

        }
    }
}

折半插入排序是對(duì)直接插入排序的簡(jiǎn)單改進(jìn)。

此處介紹的折半插入，其實(shí)就是通過(guò)不斷地折半來(lái)快速確定第i個(gè)元素的插入位置，這實(shí)際上是一種查找算法：折半查找。Java的Arrays類(lèi)里的binarySearch()方法，就是折半查找的實(shí)現(xiàn)，用于從指定數(shù)組中查找指定元素，前提是該數(shù)組已經(jīng)處于有序狀態(tài)。

與直接插入排序的效果相同，只是更快了一些，因?yàn)檎郯氩迦肱判蚩梢愿斓卮_定第i個(gè)元素的插入位置

代碼實(shí)現(xiàn)：

//折半插入排序
public class BinaryInsertSort{
    public static void binaryInsertSort(int[] data) {
        int len = data.length;
        for (int i = 1; i < len; i++) {
            int tmp = data[i];
            int low = 0;
            int high = i - 1;
            while(low <= high) {
                int mid = (low + high) / 2;
                if (tmp > data[mid]) {
                    low = mid + 1;
                }
                else {
                    high = mid -1;
                }

            }for (int j = i;j > low ; j-- ) {
                data[j] = data[j - 1 ];
            }
            data[low] = tmp;
        }
    }

    public static void main(String[] args) {
        int[] data = {5,2,7,3,9};
        binaryInsertSort(data);
        for (int d : data) {
            System.out.print(" " + d);
        }
    }
}

/**
 * Created by guo on 2018/2/2.
 * 二分查找法(折半查找)：前提是在已經(jīng)排好序的數(shù)組中，通過(guò)將待查找的元素
 * 與中間索引值對(duì)應(yīng)的元素進(jìn)行比較，若大于中間索引值對(duì)應(yīng)的元素，去右半邊查找，
 * 否則，去左邊查找。依次類(lèi)推。直到找到位置；找不到返回一個(gè)負(fù)數(shù)
 */
public class BinarySearchSort {
    public static void main(String[] args) {
        //必須保證數(shù)列是有序的
        int[] nums = {12, 32, 55, 67, 87, 98};
        int i = binarySearch(nums, 87);
        System.out.println("查找數(shù)的下標(biāo)為：" + i);   //輸出下標(biāo)為4
    }

    /**
     * 二分查找算法
     *
     * @param nums
     * @param key
     * @return
     */
    public static int binarySearch(int[] nums, int key) {
        int start = 0;             //開(kāi)始下標(biāo)
        int end = nums.length - 1; //結(jié)束下標(biāo)
        while (start <= end) {     //開(kāi)始位置不能穿過(guò)結(jié)束位置 --start-->|<--end--
            int middle = (start + end) / 2;
            // 如果查找的key比中間的大，則去掉左邊的值
            if (key > nums[middle]) {
                start = middle + 1;
             //如果查找的key比中間的小，則去掉右邊的。
            } else if (key < nums[middle]) {
                end = middle - 1;             //結(jié)束位置需要向前移一位。
            } else {
                return middle;
            }
        }
        //找不到則返回-1
        return -1;
    }
}

先到這里吧，后續(xù)還得多敲幾遍，需要學(xué)習(xí)的太多了，gogogo。

給大家放兩個(gè)鏈接，GitHub、GitHub。里面收集的文章非常有水準(zhǔn)，點(diǎn)進(jìn)去不會(huì)失望的。