基于比较的排序算法汇总 选择排序法 插入排序法 归并排序法 快速排序法 堆排序法 冒泡排序法 希尔排序法

# 七大基于比较的排序算法汇总 基于比较的排序算法汇总，这些排序算法之所以能够将元素进行排序 ，依赖于元素和元素之间的比较，以下的数组元素类型都需要实现Comparable接口。 #### 介绍 ##### [选择排序法](./src/com/wkq/selectionsort/SelectionSort.java) 算法思想：每次处理还没处理元素里最小的元素 ##### [插入排序法](./src/com/wkq/insertionsort/InsertionSort.java) ##### 归并排序法： O(nlogn)求解数组中逆序对个数 * 自顶向下的归并排序法 * 自底向上的归并排序法 ##### 快速排序法：随机算法 O(n)求解selectK,topK 问题 * 单路快速排序法: 如果数据中包含大量重复元素的话，也会退化成一个O(n^2)级别的算法，快速排序法不应该采用单路快速排序法 * 双路快速排序法： * 三路快速排序法： ##### 堆排序法 ： 堆；优先队列，求解selectK,topK 问题 * 把所有的数据都扔进一个堆中，再依次从堆中取出这些数据，取出来的过程其实就已经排好序了，但是这样做空间是O(n)的 * 可以通过Heapify在原地进行堆排序，这样空间不仅变成了O(1)级别，在性能上也变优了一些 ##### [冒泡排序法](./src/com/wkq/bubblesort/BubbleSort.java) O(n^2)的排序算法 基本思想：每次比较相邻的两个元素 第i轮开始，arr[n-i,n)已经排好序 第i轮：通过冒泡在arr[n-i-1]位置上放上合适的元素 第i轮结束：arr[n-i-1,n)已排好序 ##### [希尔排序法](./src/com/wkq/shellsort/ShellSort.java)： 分组的思想 基本思想：让数组越来越有序，不能只处理相邻的逆序对 对元素间距为n/2的所有数组做插入排序 对元素间距为n/4的所有数组做插入排序 对元素间距为n/8的所有数组做插入排序 ... 对元素间距为1的所有数组做插入排序