一、交换排序
    1. 冒泡排序
    2. 快速排序
二、选择排序
    1. 简单选择排序
三、插入排序
    1. 直接插入排序
    2. 希尔排序

注：方法说明

    /**
     * 交换arr数组中位置为 i j 的元素
     * @param arr
     * @param i
     * @param j
     */
    public static void swap(int arr[], int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

一、交换排序

1. 冒泡排序

1.1 算法描述

它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小(或越大)的元素会经由交换慢慢“浮”到数列的顶端。

1.2 算法实现

1.2.1 冒泡排序（传统）

    /**
     * 冒泡排序1(传统)
     * @param arr
     * @return
     * count:105
     * change:44
     */
    public static int[] bubbleSort(int[] arr) {
        // 从第一个开始循环,外层遍历arr.length次
        for (int i = 0; i < arr.length; i++) {
            // 每次循环都从第一个开始遍历, 对比arr.length-1-i次,外层每循环一次就有一个元素确定位置
            for (int j = 0; j < arr.length - 1 -i; j++) {
                // 从大到小排序
                if (arr[j] > arr[j+1]) {
                    swap(arr, j, j+1);
                }
            }
        }
        return arr;
    }

1.2.2 冒泡排序2（单头改进）

    /**
     * 冒泡排序2(改进)
     * @param arr
     * @return
     * count:77
     * change:44
     */
    public static int[] bubbleSort2(int[] arr) {
        // 初始时，最后位置不变
        int i = arr.length - 1;
        while(i > 0) {
            int flag = 0;   // 初始化交换位置
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[j+1]) {
                    flag = j;   // 记录交换的位置
                    swap(arr, j, j+1);
                }
            }
            i = flag;   // 为下一趟排序做准备
        }
        return arr;
    }

1.2.3 冒泡排序3（两头冒泡）

    /**
     * 冒泡排序3(改进)
     * @param arr
     * @return
     */
    public static int[] bubbleSort3(int[] arr) {
        int low = 0;                // 开始位置
        int high = arr.length -1;   // 最后位置
        int i;
        while(low < high) {
            for (i = low; i < high; i++) {  //正向冒泡,找到最大值
                if (arr[i] > arr[i+1]) {
                    swap(arr, i, i+1);
                }
            }
            --high;     // 修改high值,前移一位
            for (i = high; i > low; i--) {  //反向冒泡,找到最小值
                if (arr[i] < arr[i-1]) {
                    swap(arr, i, i-1);
                }
            }
            ++low;      // 修改low值,后移一位
        }
        return arr;
    }

1.2.4 冒泡排序4(两头冒泡改进)

    /**
     * 冒泡排序4(改进)
     * @param arr
     * @return
     */
    public static int[] bubbleSort4(int[] arr) {
        int low = 0;                // 开始位置
        int high = arr.length -1;   // 最后位置
        int i;
        while(low < high) {
            int flagLow=0,flagHigh = 0;
            for (i = low; i < high; i++) {  //正向冒泡,找到最大值
                if (arr[i] > arr[i+1]) {
                    flagHigh = i;
                    swap(arr, i, i+1);
                }
            }
            high = flagHigh;        // 修改high值
            for (i = high; i > low; i--) {  //反向冒泡,找到最小值
                if (arr[i] < arr[i-1]) {
                    flagLow = i;
                    swap(arr, i, i-1);
                }
            }
            low = flagLow;      // 修改low值
            if (flagLow == 0 || flagHigh == 0) {
                break;
            }
        }
        return arr;
    }

1.3 算法分析

• 最佳情况：T(n) = O(n)
• 最差情况：T(n) = O(n^2)
• 平均情况：T(n) = O(n^2)

2.快速排序

2.1 算法描述

• 原理：选择一个关键值作为基准值（一般选择第一个元素为基准元素），比基准值大的都在右边序列（一般为无序的），比基准值小的都在左边序列（一般为无序的）
• 具体过程：一次循环过程为：从后往前比较，用基准值和最后一个值比较，如果比基准值小的交换位置，如果没有继续比较下一个，直到找到第一个比基准值小的值才交换。找到这个值之后，又从前往后开始比较，如果有比基准值大的，交换位置，如果没有继续比较下一个，直到找到第一个比基准值大的值才交换。直到从前往后的比较索引>从后往前比较的索引，结束第一次循环

2.2 算法实现

2.2.1 传统快速排序

    /**
     * 快速排序
     * @param arr
     * @return
     */
    public static void quickSort(int[] arr, int left, int right) {
        int key = arr[left],    // 基准元素
                start = left,
                end = right;
        while(start < end) {
            // 从后往前比较，找到第一个比基准元素小的元素
            while(end > start && arr[end] > key) {
                end --;
            }
            // 交换两个元素的位置
            if (arr[end] < key) {
                swap(arr, start++, end);
            }
            // 从前往后比较，知道第一个比基准元素大的元素
            while(end > start && arr[start] <= key) {
                start++;
            }
            // 交换两个元素的位置
            if (arr[start] > key) {
                swap(arr, start, end--);
            }
        }
        
        if (start > left) {
            quickSort(arr, left, start-1);
        }
        if (end < right) {
            quickSort(arr, end+1, right);
        }
    }

2.3 算法分析

• 最佳情况：T(n) = O(nlogn)
• 最差情况：T(n) = O(n2)
• 平均情况：T(n) = O(nlogn)
• 快速排序是一种不稳定的排序方法

二、选择排序

1.简单选择排序

1.1 算法描述

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

1.2 算法实现

1.2.1 传统选择排序

    /**
     * 选择排序（传统）
     * @param arr
     * @return
     */
    public static int[] selectionSort(int[] arr) {
        int len = arr.length;
        int minIndex;   // 最小索引
        for (int i = 0; i < len - 1; i++) {
            minIndex = i;
            for (int j = i + 1; j < len; j++) {
                if (arr[j] < arr[minIndex]) {   // 寻找最小的数
                    minIndex = j;               // 保存最小数的索引
                }
            }
            if (i == minIndex) {
                continue;
            }
            swap(arr, minIndex, i);
        }
        return arr;
    }

1.2.2 两头选择排序

    /**
     * 选择排序（改进：两头选择）
     * @param arr
     * @return
     */
    public static int[] selectionSort2(int[] arr) {
        int low = 0,
                high = arr.length - 1;
        while(low < high) {
            int minIndex = low,
                    maxIndex = high;
            for (int i = low; i < high; i++) {
                if (arr[i] < arr[minIndex]) {   // 寻找最小的数
                    minIndex = i;               // 保存最小数的索引
                }
            }
            swap(arr, minIndex, low++);
            for (int i = high; i > low; i--) {
                if (arr[i] > arr[maxIndex]) {   // 寻找最大的数
                    maxIndex = i;               // 保存最大数的索引
                }
            }
            swap(arr, maxIndex, high--);
        }
        return arr;
    }

1.3 算法分析

• 最佳情况：T(n) = O(n2)
• 最差情况：T(n) = O(n2)
• 平均情况：T(n) = O(n2)

三、插入排序

1. 直接插入排序

1.1 算法描述

它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间

1.2 算法实现

1.2.1 插入排序(传统)

• 具体算法描述
  1. 从第一个元素开始，该元素可以认为已经被排序
  2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
  3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
  4. 重复步骤3，直到找到已排序的元素小于或等于新元素的位置
  5. 将新元素插入到该位置后
  6. 重复步骤2~5
• 算法代码实现

    /**
     * 插入排序
     * @param arr
     * @return
     */
    public static int[] insertSort(int[] arr) {
        int len= arr.length;
        int temp,j; // 进行排序的当前值，已经排序好的下标
        for (int i = 1; i < len; i++) {
            temp = arr[i];
            j = i - 1;
            while (j >= 0 && arr[j] > temp) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = temp;
        }
        return arr;
    }

1.2.2 插入排序改进（二分插入）

• 具体算法描述
  1. 从第一个元素开始，该元素可以认为已经被排序
  2. 取出下一个元素，在已经排序的元素序列中取出中间元素与新元素对比
  3. 如果该元素（已排序）大于新元素，则用该元素左侧的元素重复该步骤，如果该元素（已排序）小于新元素，则用该元素右侧的元素重复该步骤
  4. 直到找到已排序的元素小于或等于新元素的位置
  5. 将新元素插入到该位置后
  6. 重复步骤2~5
• 算法代码实现

    /**
     * 插入排序2(二分插入)
     * @param arr
     * @return
     */
    public static int[] insertSort2(int[] arr) {
        int len= arr.length;
        int left,right,temp;    
        for (int i = 1; i < len; i++) {
            temp = arr[i];
            left = 0;
            right = i - 1;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (arr[mid] > temp) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            for (int j = i - 1; j >= left; j--) {
                arr[j + 1] = arr[j];
            }
            arr[left] = temp;
        }
        return arr;
    }

1.3 算法分析

• 最佳情况：输入数组按升序排列。T(n) = O(n)
• 最坏情况：输入数组按降序排列。T(n) = O(n2)
• 平均情况：T(n) = O(n2)
• 直接插入排序是稳定的

2. 希尔排序

2.1 算法描述

希尔排序是插入排序的一种高效率的实现，也叫缩小增量排序。简单的插入排序中，如果待排序列是正序时，时间复杂度是O(n)，如果序列是基本有序的，使用直接插入排序效率就非常高。希尔排序就利用了这个特点。基本思想是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时再对全体记录进行一次直接插入排序。

2.2 算法实现

• 具体算法描述

1. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
2. 按增量序列个数k，对序列进行k 趟排序；
3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

• 代码实现

2.2.1 希尔排序1

    /**
     * 希尔排序
     * @param arr
     * @return
     */
    public static int[] shellSort(int[] arr) {
        int temp,gap,len;
        gap = len = arr.length;
        while(true) {
            gap = gap / 2;
            for (int i = 0; i < gap; i++) {
                for (int j = i + gap; j < len; j = j + gap) {
                    temp = arr[j];
                    int k;
                    for (k = j - gap; k >= 0 && arr[k] > temp; k = k -gap) {
                        arr[k + gap] = arr[k];
                    }
                    arr[k + gap] = temp;
                }
            }
            if (gap == 1) {
                break;
            }
        }
        return arr;
    }

2.2.2 希尔排序2

    /**
     * 希尔排序2
     * @param arr
     * @return
     */
    public static int[] shellSort2(int[] arr) {
        int len = arr.length,
            gap,temp,i,j;
        for (gap = len / 2; gap > 0; gap = gap / 2) {
            for (i = gap; i < len; i++) {
                temp = arr[i];
                for (j = i-gap; j >= 0 && arr[j] > temp; j -= gap) {
                    arr[j+gap] = arr[j];
                }
                arr[j+gap] = temp;
            }
        }
        return arr;
    }
    

2.3 算法分析

• 最佳情况：T(n) = O(nlog2 n)
• 最坏情况：T(n) = O(nlog2 n)
• 平均情况：T(n) =O(nlog n)
• 希尔排序因为是跳跃式记录，故不是一个稳定的排序算法。