排序算法，基本的高级语言都有一些提供。C语言有qsort()函数，C++有sort()函数，java语言有Arrays类(不是Array)。用这些排序时，都可以写自己的排序规则。

Java API对Arrays类的说明是：此类包含用来操作数组（比如排序和搜索）的各种方法。

 

上面两句话话是对其他博客上的引用，不清楚是那篇了，所以就不贴地址了，其实除了数组，java对集合也有sort()的排序方法，这里详细写一下对数组的几种常用的排序方法。

 

 

快速排序是对选择排序和冒泡排序的优化

 

选择排序我觉得是最好理解的，冒泡排序推荐看下：https://www.cnblogs.com/shen-hua/p/5422676.html，写的很清楚

 

冒泡排序：

 

    @Test
    public void test4() {
        int a[] = {49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15, 35, 25, 53, 51};
        for(int i=0;i<a.length-1;i++) {
            for (int j = 0; j < a.length - 1-i; j++) {
                if (a[j] > a[j + 1]) {
                    int t = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = t;
                }

            }
        }
        System.out.println(Arrays.toString(a));
    }

 

 

 

 

 

 

选择排序：

    @Test
    public void test2() {
        int a[] = {49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15, 35, 25, 53, 51};
        for (int i = 0; i < a.length; i++) {
            for (int j = i + 1; j < a.length; j++) {
                if (a[i] > a[j]) {
                    a[j] = a[i] + a[j];
                    a[i] = a[j] - a[i];
                    a[j] = a[j] - a[i];
                }
            }
        }

 

递归排序：递归的本质---自身调用自身

 

# 求阶乘
   
 public static void main(String[] args) {
        System.out.println(f(5));
        System.out.println(5 * 4 * 3 * 2 * 1);
    }

    public static int f(int n) {
        if (1 == n || 2 == n)
            return n;
        else
            return n * f(n - 1);
        /*
        * 5*f4
        * 5*4*f3
        * 5*4*3*f2
        * 5*4*3*2
        * */
    }

 

    /*
        斐波那契数列: 0、1、1、2、3、5、8
        f0 = 0; f1 = 1; fn = f(n-1) + f(n - 2) （n >= 2）
        
    */
    public static void main(String[] args) {
        System.out.println(f(5));
    }    
        public static int f(int n) {
            if (n == 1 || n == 2) {
                return 1;
            } else {
                return f(n - 1) + f(n - 2);
            }
        }

快速排序分治法就用到了递归思想，主要有挖坑法和下标交换法，分治也用到交换思想，

挖坑法

package study.test;

import java.util.Arrays;

public class Mysort {
    public static void quickSort(int[] arr, int startIndex, int endIndex) {
// 递归结束条件：startIndex大等于endIndex的时候(即每部分数组拆分至一个元素)
        if (startIndex >= endIndex) {
            return;
        }
// 得到基准元素位置
        int pivotIndex = partition(arr, startIndex, endIndex);
// 用分治法递归数列的两部分
        quickSort(arr, startIndex, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, endIndex);
    }

    private static int partition(int[] arr, int startIndex, int endIndex) {
        System.out.println("the begin : " + Arrays.toString(arr));
// 取第一个位置的元素作为基准元素
        int pivot = arr[startIndex];
        int left = startIndex;
        int right = endIndex;
// 坑的位置，初始等于pivot的位置
        int index = startIndex;
//大循环在左右指针重合或者交错时结束
        while (right >= left) {
//right指针从右向左进行比较
            while (right >= left) {
                if (arr[right] < pivot) {
                    arr[left] = arr[right];
                    index = right;
                    left++;
                    break;
                }
                right--;
                System.out.println("the in one: " + Arrays.toString(arr));
            }
//left指针从左向右进行比较
            while (right >= left) {
                if (arr[left] > pivot) {
                    arr[right] = arr[left];
                    index = left;
                    right--;
                    break;
                }
                left++;
                System.out.println("the in two: " + Arrays.toString(arr));
            }
        }
        arr[index] = pivot;
        System.out.println("the end : " + Arrays.toString(arr));
        return index;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{4, 7, 6, 5, 3, 2, 8, 1};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}


非交换思想，使用数组拆分

package study.test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class JustSort {
    public static int partition(int[] arr, int start, int end) {
        int mid = start + (end - start) / 2;    //每次取中位数为基准元素
        System.out.println("基准元素取中 mid :" + arr[mid]);
        List<Integer> left = new ArrayList();
        List<Integer> rigth = new ArrayList();
        for (int i = 0; i <= end; i++) {    //遍历数组，使用集合分别存储大于基准数和小于基准数的元素
            if (i != mid) {     //遍历过错中先隔离基准数，待遍历完毕后存储基准数，保证基准数在数组中下标不变
                if (arr[i] <= arr[mid]) {
                    left.add(arr[i]);
                }
                if (arr[i] > arr[mid]) {
                    rigth.add(arr[i]);
                }
            }
        }
        int index = left.size();    //获取数组分治后下一轮数组的长度作为下一次排序的范围
        left.add(arr[mid]);     //添加基准数
        left.addAll(rigth);     //此时left集合中存储当次排序后元素
        for (int i = 0; i < left.size(); i++) {
            arr[i] = left.get(i);       //将排序后元素从list更新到原数组
        }
        System.out.println(Arrays.toString(arr));
        return index;
    }

    public static void sort(int[] array, int start, int end) {
        if (start >= end) {     //当拆分数组元素仅有1个时，出现截取数组终止下标比开始下标小1或者相等(第一个元素时相等),此时无需排序
            return;
        }
        int mid = partition(array, start, end);
        sort(array, start, mid - 1);    //根据基准数切割数组，选取基准数左边数组
        sort(array, mid + 1, end);      //选取基准数右边数组
    }

    public static void main(String[] args) {
        int[] arr = {4, 7, 6, 5, 3, 2, 8, 1};
        System.out.println("源数组： \n" + Arrays.toString(arr));
        sort(arr, 0, arr.length - 1);
        System.out.println("排序结果： \n" + Arrays.toString(arr));
    }
}


 

前言
快速排序（Quicksort）是对冒泡排序的一种改进。
快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
整个过程，我都写到注释里面了。如果不明白，可以打开冒泡排序的章节，用动画的形式来自己观看一下。
代码
package 
总结
点击关注不迷路哦，后续有更新会推送给您的。

用java实现了冒泡排序和快速排序，冒泡还是比较简单的，但快速排序采坑了，网上有很多代码是有问题的，最后通过分析和实践，终于弄明白了，分享出来以供大家一起学习~~

快速排序写了2种实现方法，原理都是一样的，快排的平均时间复杂度是O(N*logN)

实现思路：（基于递归实现） 

1.选一个值作为中轴（理想情况选中值最好，但一般使用数组的第一个值）。 

2.基于中轴，将数组分为两部分，较小的分在左边，较大的分在右边。 

3.对两个子数组分别重复上述过程进行排序。

import java.util.ArrayList;
import java.util.Arrays;

/**
 * Created by admin on 2017/12/8.
 */
public class SortArray {
    public static void main(String[] args) {
        final int[] arr1 = {3, 12, 3, 15, 2, 89, 45};
        final int[] arr2 = {3, 12, 3, 15, 2, 89, 45};
        final int[] arr3 = {3, 12, 3, 15, 2, 89, 45};
        //调用冒泡
        int[] sortResult1 = sort1(arr1);
        //调用快速
        int start = 0;
        int end = arr2.length-1;
        int[] sortResult2 = quickSort(arr2,start,end);
        int[] sortResult3 = quickSort2(arr3, start, end);

        System.out.println(Arrays.toString(sortResult1));
        System.out.println(Arrays.toString(sortResult2));
        System.out.println(Arrays.toString(sortResult3));
    }

    //冒泡排序 从大到小
    public static int[] sort1(int[] arr){
        for (int i = arr.length-1; i > 0; i--){
            for (int j=0; j<i; j++){
                if (arr[j]<arr[j+1]){
                    int temp = arr[j+1];
                    arr[j+1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        return arr;
    }

    //快速排序方法一
    private static int[] quickSort(int[] arr, int low, int high){
        if (low < high){
            int index = partitions(arr, low, high);
            quickSort(arr, low, index-1); //递归排序左子数组
            quickSort(arr, index+1, high); //递归排序右子数组
        }
        return arr;
    }
    public static int partitions(int[] arr, int low, int high){
        //arr2 = {3, 12, 3, 15, 2, 89, 45}
        int index = arr[low]; //中轴
        while (low < high){
            while (low < high && arr[high] >= index)
                high--; //arr[high]一直大于index，那么就一直减小high
            arr[low] = arr[high];  //直到遇到比index小的值 交换到左端

            while (low < high && arr[low] <= index)
                low++;  //arr[low]一直小于index，那么就一直增大low
            arr[high] = arr[low];  //直到遇到比index大的值 交换到右端
        }
        arr[low] = index;
        //返回的是中轴的位置
        return low;
    }

    //快速排序方法二
    public static int[] quickSort2(int[] arr,int l,int r){
        if(l>=r)
            return arr;
        int i = l; int j = r; int key = arr[l];//选择第一个数为key
        while(i<j){
            while(i<j && arr[j]>=key)//从右向左找第一个小于key的值
                j--;
            if(i<j){
                arr[i] = arr[j];
                i++;
            }
            while(i<j && arr[i]<key)//从左向右找第一个大于key的值
                i++;
            if(i<j){
                arr[j] = arr[i];
                j--;
            }
        }
        arr[i] = key;
        quickSort2(arr, l, i-1);//递归调用
        quickSort2(arr, i+1, r);//递归调用
        return arr;
    }
}

写在前面

对于经典的排序算法大家都很熟悉，这里提供一个未经过严格测试的快速排序算法代码，仅供学习之用。

另外，说几点在写算法时的一般规律或者说快速记忆方法。

当然，对于分治类型的算法，一般都存在递归解法和非递归解法两种，这里也给出两种实现。



代码实现



package com.nggirl.test.sort;

import java.util.HashSet;
import java.util.Set;

public class QuickSort {

    public static void main(String[] args) {
        int[] sortArray = {1,3,2,6,4,5,9,7,8};
        new QuickSort().sort(sortArray, 0, 8);

        for(int x : sortArray){
            System.out.println(x);
        }


        System.out.println("=============================");
        new QuickSort().sortNonRecurse(sortArray, 0, 8);

        for(int x : sortArray){
            System.out.println(x);
        }
    }

    private void sort(int[] sortArray, int start, int end){
        if(sortArray == null || sortArray.length == 0){
            return;
        }
        if(start > end || start > sortArray.length || end - start > sortArray.length){
            return;
        }

        int pivot = pivot(sortArray, start, end);
        sort(sortArray, start, pivot-1);
        sort(sortArray, pivot+1, end);
    }

    private void sortNonRecurse(int[] sortArray, int start, int end){
        if(sortArray == null || sortArray.length == 0){
            return;
        }
        if(start > end || start > sortArray.length || end - start > sortArray.length){
            return;
        }

        class PartValue{
            private int start;
            private int end;

            public PartValue(int start, int end){
                this.start = start;
                this.end = end;
            }

            public int getStart() {
                return start;
            }
            public int getEnd() {
                return end;
            }
        }

        Set<PartValue> parts = new HashSet<PartValue>();
        parts.add(new PartValue(start, end));

        while(parts.size() != 0){
            Set<PartValue> nextParts = new HashSet<PartValue>();

            for(PartValue part : parts){
                int pivot = pivot(sortArray, part.getStart(), part.getEnd());
                if(part.getStart() < pivot-1){
                    nextParts.add(new PartValue(part.getStart(), pivot-1));
                }
                if(pivot+1 < part.getEnd()){
                    nextParts.add(new PartValue(pivot+1, part.getEnd()));
                }
            }

            parts = nextParts;
        }
    }

    private int pivot(int[] sortArray, int start, int end){
        int cur = sortArray[start];

        while(start < end){
            //右侧小的往左移动
            while(end > start && sortArray[end] > cur){
                end--;
            }
            if(end > start){
                sortArray[start++] = sortArray[end];
                sortArray[end] = cur;
            }

            //左侧大的右移
            while(start < end && sortArray[start] <= cur){
                start++;
            }
            if(start < end){
                sortArray[end--] = sortArray[start];
                sortArray[start] = cur;
            }
        }

        return start;
    }

}



关于递归实现

递归实现的思路很简单，关键是要把握两点。1.终止条件判断；2.递归调用方法。比如，上述代码中的sort方法：



private void sort(int[] sortArray, int start, int end){
        if(sortArray == null || sortArray.length == 0){
            return;
        }
        if(start > end || start > sortArray.length || end - start > sortArray.length){
            return;
        }

        int pivot = pivot(sortArray, start, end);
        sort(sortArray, start, pivot-1);
        sort(sortArray, pivot+1, end);
    }

其中，第二个if中的start > end是递归的终止条件，其他的都是入参检查。

后续的，pivot方法和分开两次调用的sort，就是递归过程。

对于正式的代码，一般来说在递归主方法调用的前面会加上一个包装方法，用来处理条件检查或者主方法所需数据的准备。类似于：



packSort(int[] sortArray, int start, int end){
    if(sortArray == null || sortArray.length == 0){
        return;
    }
    if(start > end || start > sortArray.length || end - start > sortArray.length){
        return;
    }

    sort(sortArray, start, end);
}

private void sort(int[] sortArray, int start, int end){
        //终止条件
        if(start > end){
            return;
        }

        //递归过程---裂变
        int pivot = pivot(sortArray, start, end);
        sort(sortArray, start, pivot-1);
        sort(sortArray, pivot+1, end);
}



非递归实现

对于非递归实现，如果你熟悉二叉树的遍历过程那么大概应该知道：深度优先遍历要用堆栈去辅助，广度优先遍历要用队列去辅助。

对于分治类型的算法都可以类比于树的广度优先遍历，也就是用队列做辅助存储，把后续需要递归遍历的入参插入到队列尾部。

当然，存储的方式不一定必须使用队列，但原理都是一样的，就是存储后续遍历的入参，也就是条件。

这里使用的是不断更新的一个HashSet去存储下一个水平层的所有遍历条件。（可以把二分的过程，想象成一个树状结构，每一次递归，完成树状的一个水平层。）

递归的条件，这里放到了一个局部内部类里面(因为这个类的有效范围仅仅是sortNonRecurse里面，所以使用了局部的内部类)：

class PartValue{
    private int start;
    private int end;

    public PartValue(int start, int end){
        this.start = start;
        this.end = end;
    }

    public int getStart() {
        return start;
    }
    public int getEnd() {
        return end;
    }
}

当然，这里选择HashSet可以看做一个败笔，用一个ArrayList相对来说更能够节省一些不必要的空间。

pivot这个关键方法

这里简单说一下pivot这个方法的过程（这里没有给出详细的解说，仅是给出了一个记忆的线索）：

首先，选择最左侧的值作为pivot-value； 

然后，用3个while循环确定pivot的最终位置。内层的两个循环先把右侧第一个小于pivot-value的值移到左侧。再把左侧第一个大于pivot-value的值移动到右侧。由外边的循环不断的完成这个过程。直到start=end为止。 

最后，返回start值，此时的start就是要找的划分为止，也就是pivot。

对于第一个步骤还可以采用随机选取的方式，避免sortArray有序时带来的低效。