6、快速排序（Quick Sort）
快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，以中轴元素为基准，左边全部元素比右边小（大），然后左右两边再分别找其中轴元素，以此往复，到最后数组的大小为1，此时每个元素都处于有序的位置。
排序过程简单描述：
1、从数列中挑出一个元素，称为 “基准”（pivot ）；
2、重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。
3、递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。
/**
* @author Li DongWei
* 快速排序
*/
public class QuickSort {
public static void main(String[] args) {
int[] arr = {5, -1, 3, 6, 4, 2, 2};
quickSort(arr, 0, arr.length - 1);
for (int a : arr){
System.out.println(a);
}
}
public static void quickSort(int[] arr, int i, int j) {
if (i < j) {
quickPass(arr, i, j);
quickSort(arr, i + 1, j);
quickSort(arr, i, j - 1);
}
}
public static int quickPass(int[] arr, int i, int j) {
int pivot = arr[i];
while (i < j) {
while (i < j && arr[j] >= pivot) {
j--;
}
if (i < j) {
arr[i] = arr[j];
i++;
}
while (i < j && arr[j] <= pivot) {
i++;
}
if (i < j) {
arr[j] = arr[i];
j--;
}
}
arr[i] = pivot;
return i;
}
}
算法分析
性质：1、时间复杂度：O(nlogn) 2、空间复杂度：O(logn) 3、非稳定排序 4、原地排序
最佳情况：T(n) = O(nlogn) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(nlogn)
7、堆排序（Heap Sort）
堆排序（Heapsort） 是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
排序过程简单描述：
1、将初始待排序数组(a1, a2, a3, ... , a(n-1))构建成大顶堆，此堆为初始的无序区；
2、将堆顶元素 a[0] 与最后一个元素 a[n-1] 交换，此时得到新的无序区 (a1, a2, ... , a(n-1)) 和新的有序区 a(n) ,且满足 a[1,2…n-1] <= a[n]；
3、由于交换后新的堆顶 a[1 ]可能违反堆的性质，因此需要对当前无序区 (a1, a2, ... , a(n-1))调整为新堆，然后再次将 a[1] 与无序区最后一个元素交换，得到新的无序区 (a1, a2, … , an-2) 和新的有序区 (a(n-1), a(n))。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
/**
* @author Li DongWei
* @date 2020/3/22 16:24
*/
public class HeapSort {
public static void main(String[] args) {
int[] arr = {5, -1, 3, 6, 4, 2, 2};
heapSort(arr);
for (int a : arr){
System.out.println(a);
}
}
private static void heapSort(int[] arr) {
buildHeap(arr);
for (int i = arr.length - 1; i >= 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heaping(arr, 0, i);
}
}
private static void buildHeap(int[] arr) {
int lastNode = arr.length - 1;
int farther = (lastNode - 1) / 2;
for (int i = farther; i >= 0; i--) {
heaping(arr, i, arr.length);
}
}
private static void heaping(int[] arr, int i, int n) {
if (i >= n) {
return;
}
int left = 2 * i + 1;
int right = 2 * i + 2;
int max = i;
if (left < n && arr[left] > arr[max]) {
max = left;
}
if (right < n && arr[right] > arr[max]) {
max = right;
}
if (max != i) {
int temp = arr[max];
arr[max] = arr[i];
arr[i] = temp;
heaping(arr, max, n);
}
}
}
算法分析
性质：1、时间复杂度：O(nlogn) 2、空间复杂度：O(1) 3、非稳定排序 4、原地排序
最佳情况：T(n) = O(nlogn) 最差情况：T(n) = O(nlogn) 平均情况：T(n) = O(nlogn)
8、计数排序（Counting Sort）
计数排序是一种稳定的排序算法。计数排序使用一个额外的数组C，其中第i个元素是待排序数组 A 中值等于 i 的元素的个数。然后根据数组 C 来将 A 中的元素排到正确的位置。它只能对整数进行排序。
计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
排序过程简单描述：
1、把数组元素作为数组的下标
2、用一个临时数组统计每个元素出现的次数，例如 temp[i] = m, 表示元素 i 一共出现了 m 次
3、把临时数组统计的数据从小到大汇总起来，此时汇总起来是数据是有序的数组。
/**
* @author Li DongWei
* 计数排序
*/
public class CountingSort {
public static void main(String[] args) {
int[] arr = {5, -1, 3, 6, 4, 2, 2};
int min = arr[0], max = arr[0];
for (int i = 1; i < arr.length; i++){
if (arr[i] < min){
min = arr[i];
}
if (arr[i] > max){
max = arr[i];
}
}
int[] count = new int[max - min + 1];
for (int i = 0; i < arr.length; i++){
count[arr[i] - min]++;
}
int k = 0, j;
for (int i = 0; i < count.length; i++) {
j = count[i];
while (j > 0){
arr[k++] = i + min;
j--;
}
}
for (int a : arr){
System.out.println(a);
}
}
}
算法分析
1、时间复杂度：O(n+k) 2、空间复杂度：O(k) 3、稳定排序 4、非原地排序
最佳情况：T(n) = O(n+k) 最差情况：T(n) = O(n+k) 平均情况：T(n) = O(n+k)
9、桶排序（Bucket Sort）
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。
桶排序的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）
排序过程简单描述：
1、人为设置一个BucketSize，作为每个桶所能放置多少个不同数值（例如当BucketSize==5时，该桶可以存放｛1,2,3,4,5｝这几种数字，但是容量不限。
2、遍历输入数据，并且把数据一个一个放到对应的桶里去；
3、对每个不是空的桶进行排序，可以使用其它排序方法，也可以递归使用桶排序；
从不是空的桶里把排好序的数据拼接起来。
/**
* @author Li DongWei
* 桶排序
*/
public class BucketSort {
public static void main(String[] args) {
int[] arr = {5, -1, 3, 6, 4, 2, 2};
int min = arr[0], max = arr[0];
for (int i = 1; i < arr.length; i++){
if (arr[i] < min){
min = arr[i];
}
if (arr[i] > max){
max = arr[i];
}
}
int d = max - min, bucket = d / 5 + 1;
ArrayList<LinkedList<Integer>> list = new ArrayList<>(bucket);
for (int i = 0; i < bucket; i++){
list.add(new LinkedList<Integer>());
}
for (int i = 0; i < arr.length; i++){
list.get((arr[i] - min) / d).add(arr[i] - min);
}
for (int i = 0; i < bucket; i++){
Collections.sort(list.get(i));
}
int k = 0;
for (int i = 0; i < bucket; i++){
for (Integer t : list.get(i)){
arr[k++] = t + min;
}
}
for (int a : arr){
System.out.println(a);
}
}
}
算法分析
1、时间复杂度：O(n+k) 2、空间复杂度：O(n+k) 3、稳定排序 4、非原地排序
最佳情况：T(n) = O(n+k) 最差情况：T(n) = O(n+k) 平均情况：T(n) = O(n2)
10、基数排序（Radix Sort）
基数排序也是非比较的排序算法，对每一位进行排序，从最低位开始排序，复杂度为O(kn)为数组长度，k为数组中的数的最大的位数；
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。
排序过程简单描述：
1、取得数组中的最大数，并取得位数；
2、arr为原始数组，从最低位开始取每个位组成radix数组；
3、对radix进行计数排序（利用计数排序适用于小范围数的特点）；
/**
* @author Li DongWei
* 基数排序
*/
public class RadixSort {
public static void main(String[] args) {
int[] arr = {5, -1, 3, 6, 4, 2, 2};
int min = arr[0], max = arr[0];
for (int i = 1; i < arr.length; i++){
if (arr[i] < min){
min = arr[i];
}
if (arr[i] > max){
max = arr[i];
}
}
if (min < 0){
for (int i = 0; i < arr.length; i++){
arr[i] -= min;
}
}
int num = 1;
while (max / 10 > 0){
num++;
max /= 10;
}
ArrayList<LinkedList<Integer>> bucketList = new ArrayList<>(10);
for (int i = 0; i < 10; i++){
bucketList.add(new LinkedList<Integer>());
}
for (int i = 0; i < num; i++){
for (int j = 0; j < arr.length; j++){
int radio = (arr[j] / (int)Math.pow(10, i)) % 10;
bucketList.get(radio).add(arr[j]);
}
int k = 0;
for (int j = 0; j < 10; j++){
for (Integer t : bucketList.get(j)){
arr[k++] = t;
}
bucketList.get(j).clear();
}
}
if (min < 0){
for (int i = 0; i < arr.length; i++){
arr[i] += min;
}
}
for (int a : arr){
System.out.println(a);
}
}
}
算法分析
性质：1、时间复杂度：O(kn) 2、空间复杂度：O(n+k) 3、稳定排序 4、非原地排序
最佳情况：T(n) = O(n * k) 最差情况：T(n) = O(n * k) 平均情况：T(n) = O(n * k)
参考文章：
十大经典排序算法、超详细十大经典排序算法总结（java代码）c或者cpp的也可以明白、
十大经典排序算法超详细总结（含JAVA代码实现）
