前言十大排序
一冒泡排序
- 1.1 代码实现
- 1.2 总结
二选择排序
- 2.1 代码实现
- 2.2 总结
三插入排序
- 3.1 代码实现
- 3.2 总结
四希尔排序
- 4.1 代码实现
- 4.2 总结
五归并排序
- 5.1 代码实现
- 5.2 总结
六快速排序
- 6.1 代码实现
- 6.2 总结
七堆排序
- 7.1 代码实现
- 7.2 总结
八计数排序
- 8.1 代码实现
- 8.2 总结
九桶排序(Bucket Sort）
- 9.1 代码实现
- 9.2 总结
十基数排序(Radix Sort)
- 10.1 代码实现
- 10.2 总结

前言十大排序

下面我们用2个小时时间过下10个排序。算法-入门篇之十大排序 - 图1

一冒泡排序

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。
原理：每次比较前后两个值

比较相邻元素。如果前一个元素比后一个元素大，则交换这两个元素位置。
对每一对元素重复操作，直至比较完成。

1.1 代码实现

    /**
     * 冒泡排序
     * @param array
     * @return
     */
    public static int[] bubbleSort(int[] array) {
         int len = arr.length;
        //从0开始，依次向后遍历，每次把最大的移动到最后
        for (int i = 0; i < len; i++) {
            //出勤最后的大值，比较前面的乱序
            for (int j = 0; j < len - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        return arr;
    }
    public static void main(String[] args) {
        System.out.println(JSONObject.toJSONString(SortTest.bubbleSort(new int[]{6, 5, 4, 3, 2, 1})));
    }

1.2 总结

最佳情况：T(n) = O(n)
最差情况：T(n) = O(n2)
平均情况：T(n) = O(n2)
二选择排序
选择排序(Selection-sort)是一种简单直观的排序算法。
原理：每次获取最小值

每次遍历，都假定第一个索引处元素是最小值，然后和其他索引处值依次进行比较，如果当前索引处值大于其他某个索引处值，那么其他索引处值为最小值，交换第一个索引处和最小值所在索引处值。
以此类推，最后可以找到最小值所在索引。

2.1 代码实现

/**
     * 选择排序
     *
     * @param array
     * @return
     */
    public static int[] selectionSort(int[] arr) {
       int len = arr.length;
        //从0开始，假设第一个数最小，依次向后假设
        for (int i = 0; i < len - 1; i++) {
            int minIndex = i;
            //每次与最小的值比较后面的数据，有最小的向前提取。
            for (int j = i; j < len; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
        return arr;
    }
    public static void main(String[] args) {
        System.out.println(JSONObject.toJSONString(SortTest.selectionSort(new int[]{6, 5, 4, 3, 2, 1})));
    }

2.2 总结

最佳情况：T(n) = O(n2)
最差情况：T(n) = O(n2)
平均情况：T(n) = O(n2)
三插入排序
插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。
原理：

把所有的元素分为两组，已经排序的和未排序的；
找到未排序组中第一个元素，向已经排序组中进行插入；

3.1 代码实现

/**
     * 插入排序
     *
     * @param array
     * @return
     */
    public static int[] insertionSort(int[] arr) {
         int len = arr.length;
        //从一开始，每次新插一个
        for (int i = 1; i < len; i++) {
            //对新增后的分组，重新排序
            for (int j = i; j > 0; j--) {
                if (arr[j - 1] > arr[j]) {
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                }
            }
        }
        return arr;
    }
    public static void main(String[] args) {
        System.out.println(JSONObject.toJSONString(SortTest.insertionSort(new int[]{6, 5, 4, 3, 2, 1})));
    }

3.2 总结

最佳情况：T(n) = O(n)
最坏情况：T(n) = O(n2)
平均情况：T(n) = O(n2)
四希尔排序
1959年Shell发明，第一个突破O(n)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序**。
原理：**

选定一个增长量h，按照增长量h作为数据分组的依据，对数据进行分组；
对分好组的每一组数据完成插入排序；
减小增长量，最小减为1，重复第二步操作。

增长量h的确定：增长量h的值每一固定的规则，我们这里采用以下规则：

int h=1
while(h<5){
    h=2h+1；//3,7
}
//循环结束后我们就可以确定h的最大值；
h的减小规则为：
h=h/2

4.1 代码实现

package com.ycc.data.sort;
import com.alibaba.fastjson.JSONObject;
/**
 * 希尔排序
 *
 * @author hezhaoming
 * @date 2020/10/19
 */
public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
        int len = arr.length;
        int gap = len / 2;
        int temp;
        while (gap > 0) {
            //找到每一个待插入元素 加入gap=4，i=4，gap=4，i=5，gap=4，i=6
            for (int i = gap; i < len; i++) {
                //把待插入的元素插入到有序数列中 比较 0-5，1-6，2-7
                for (int j = i; j >= gap; j -= gap) {
                    if (arr[j - gap] > arr[j]) {
                        temp = arr[j];
                        arr[j] = arr[j - gap];
                        arr[j - gap] = temp;
                    } else {
                        break;
                    }
                }
            }
            gap = gap / 2;
        }
        System.out.println(JSONObject.toJSONString(arr));
    }
}

4.2 总结

最佳情况：T(n) = O(nlog2 n)
最坏情况：T(n) = O(nlog2 n)
平均情况：T(n) = O(nlog2n)
五归并排序
是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
原理：

尽可能将数据拆分成两个元素相等子组，并对每个子组继续拆分，直到每个子组元素个数是1为止。
将相邻的两个子组进行合并成一个有序的大组；
不断的重复步骤2，直到最终只有一个组为止。

5.1 代码实现

package com.ycc.data.sort;
import com.alibaba.fastjson.JSONObject;
/**
 * 归并排序
 *
 * @author 何兆明
 * @description 如果要排序一个数组，我们先把数组从中间分成前后两部分，然后分别对前后两部分进行排序，再将排好序的两部分数据合并在一起就可以了
 * @create 2019-04-09 11:33
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 2, 4};
        int len = arr.length;
        int[] temp = new int[arr.length];//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
        sort(arr, 0, arr.length - 1, temp);
        System.out.println(JSONObject.toJSONString(arr));
    }
    private static void sort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = (left + right) / 2;
            sort(arr, left, mid, temp);//左边归并排序，使得左子序列有序
            sort(arr, mid + 1, right, temp);//右边归并排序，使得右子序列有序
            merge(arr, left, mid, right, temp);//将两个有序子数组合并操作
        }
    }
    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int li = left;//左序列指针
        int ri = mid + 1;//右序列指针
        int t = 0;//临时数组指针
        while (li <= mid && ri <= right) {
            //左边小于右边
            if (arr[li] <= arr[ri]) {
                temp[t++] = arr[li++];
            } else {
                temp[t++] = arr[ri++];
            }
        }
        //左边提前结束，将左边剩余元素填充进temp中
        while (li <= mid) {
            temp[t++] = arr[li++];
        }
        //将右序列剩余元素填充进temp中
        while (ri <= right) {
            temp[t++] = arr[ri++];
        }
        t = 0;
        //将temp中的元素全部拷贝到原数组中
        while (left <= right) {
            arr[left++] = temp[t++];
        }
    }
}

5.2 总结

最佳情况：T(n) = O(n)
最差情况：T(n) = O(nlogn)
平均情况：T(n) = O(nlogn)
六快速排序
快速排序是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
原理：

首先设定一个分界值，通过该分界值将数组分成左右两部分。
将大于或等于分界值的数据放到到数组右边，小于分界值的数据放到数组的左边。此时左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。
然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左侧和右侧两个部分的数据排完序后，整个数组的排序也就完成了。

6.1 代码实现

package com.ycc.power;
import com.alibaba.fastjson.JSONObject;
/**
 * 快速排序
 * @author 何兆明
 * @description
 * @create 2019-04-11 17:27
 */
public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        int left, right, temp, t;
        if (low > high) {
            return;
        }
        left = low;
        right = high;
        //temp就是基准位
        temp = arr[low];
        while (left < right) {
            //先看右边，依次往左递减
            while (temp <= arr[right] && left < right) {
                right--;
            }
            //再看左边，依次往右递增
            while (temp >= arr[left] && left < right) {
                left++;
            }
            //如果满足条件则交换
            if (left < right) {
                t = arr[right];
                arr[right] = arr[left];
                arr[left] = t;
            }
        }
        //最后将基准为与i和j相等位置的数字交换
        arr[low] = arr[left];
        arr[left] = temp;
        //递归调用左半数组
        quickSort(arr, low, right - 1);
        //递归调用右半数组
        quickSort(arr, right + 1, high);
    }
    public static void main(String[] args) {
        int[] arr = {10, 7, 2, 4, 7, 62, 3, 4, 2, 1, 8, 9, 19};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(JSONObject.toJSONString(arr));
    }
}

6.2 总结

最佳情况：T(n) = O(nlogn)
最差情况：T(n) = O(n2)
平均情况：T(n) = O(nlogn)
七堆排序
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
7.1 代码实现
```java package com.ycc.power;

import com.alibaba.fastjson.JSONObject;

/**

@author 何兆明
@description 堆就是一个完全二叉树；最大堆根节点大于子节点，最小堆根节点小于子节点

@create 2019-04-10 15:12 */ public class HeapSort {

// 构建堆 public static void buildMaxHeap(int[] array) {

 if (array == null || array.length == 1)
     return;
 // 堆的公式就是 int root = 2*i, int left = 2*i+1, int right = 2*i+2;
 int cursor = array.length / 2;
 for (int i = cursor; i >= 0; i--) { // 这样for循环下，就可以第一次排序完成

// maxHeap(array, array.length, i);

     minHeap(array, array.length, i);
 }

}

// 最大堆 public static void maxHeap(int[] array, int heapSieze, int index) {

 int left = index * 2 + 1; // 左子节点
 int right = index * 2 + 2; // 右子节点
 int maxValue = index; // 暂时定在Index的位置就是最大值
 // 如果左子节点的值，比当前最大的值大，就把最大值的位置换成左子节点的位置
 if (left < heapSieze && array[left] > array[maxValue]) {
     maxValue = left;
 }
 // 如果右子节点的值，比当前最大的值大，就把最大值的位置换成右子节点的位置
 if (right < heapSieze && array[right] > array[maxValue]) {
     maxValue = right;
 }
 // 如果不相等，说明啊，这个子节点的值有比自己大的，位置发生了交换了位置
 if (maxValue != index) {
     swap(array, index, maxValue); // 就要交换位置元素
     // 交换完位置后还需要判断子节点是否打破了最大堆的性质。最大堆性质：两个子节点都比父节点小。
     maxHeap(array, heapSieze, maxValue);
 }

}

// 最小堆 public static void minHeap(int[] array, int heapSieze, int index) {

 int left = index * 2 + 1; // 左子节点
 int right = index * 2 + 2; // 右子节点
 int maxValue = index; // 暂时定在Index的位置就是最小值
 // 如果左子节点的值，比当前最小的值小，就把最小值的位置换成左子节点的位置
 if (left < heapSieze && array[left] < array[maxValue]) {
     maxValue = left;
 }
 //  如果右子节点的值，比当前最小的值小，就把最小值的位置换成左子节点的位置
 if (right < heapSieze && array[right] < array[maxValue]) {
     maxValue = right;
 }
 // 如果不相等，说明啊，这个子节点的值有比自己小的，位置发生了交换了位置
 if (maxValue != index) {
     swap(array, index, maxValue); // 就要交换位置元素
     // 交换完位置后还需要判断子节点是否打破了最小堆的性质。最小性质：两个子节点都比父节点大。
     minHeap(array, heapSieze, maxValue);
 }

}

// 数组元素交换 public static void swap(int[] array, int index1, int index2) {

 int temp = array[index1];
 array[index1] = array[index2];
 array[index2] = temp;

}

public static void heapSort(int[] array) {

 if (array == null || array.length == 1)
     return;
 buildMaxHeap(array); // 第一次排序，构建最大堆，只保证了堆顶元素是数组里最大的
 for (int i = array.length - 1; i >= 1; i--) {
     // 这个是什么意思呢？，经过上面的一些列操作，目前array[0]是当前数组里最大的元素，需要和末尾的元素交换
     // 然后，拿出最大的元素
     swap(array, 0, i);
     // 交换完后，下次遍历的时候，就应该跳过最后一个元素，也就是最大的那个值，然后开始重新构建最大堆
     // 堆的大小就减去1，然后从0的位置开始最大堆

// maxHeap(array, i, 0);

     minHeap(array, i, 0);
 }

}

public static void main(String[] args) {
    int[] array = {19, 38, 7, 36, 5, 5, 3, 2, 1, 0, 56};
    System.out.println("排序前:" + JSONObject.toJSONString(array));
    System.out.println("分割线---------------");
    heapSort(array);
    System.out.println("排序后:" + JSONObject.toJSONString(array));
}

}

```

7.2 总结

八计数排序

适合整数排序，原理统计每个数出现的个数

8.1 代码实现

8.2 总结

计数排序是一个稳定的排序算法。当输入的元素是 n 个 0到 k 之间的整数时，时间复杂度是O(n+k)，空间复杂度也是O(n+k)，其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。

算法-入门篇之十大排序

前言十大排序

一 冒泡排序

1.1 代码实现

1.2 总结

二 选择排序

2.1 代码实现

2.2 总结

三 插入排序

3.1 代码实现

3.2 总结

四 希尔排序

4.1 代码实现

4.2 总结

五 归并排序

5.1 代码实现

5.2 总结

六 快速排序

6.1 代码实现

6.2 总结

七 堆排序

7.1 代码实现

7.2 总结

八 计数排序

8.1 代码实现

8.2 总结

九 桶排序(Bucket Sort）

9.1 代码实现

9.2 总结

十 基数排序(Radix Sort)

10.1 代码实现

10.2 总结

一冒泡排序

二选择排序

三插入排序

四希尔排序

五归并排序

六快速排序

七堆排序

八计数排序

九桶排序(Bucket Sort）

十基数排序(Radix Sort)