终于把排序这个硬骨头，但是又很基础的知识点，自己手撕了一遍！之前，使用Python看着算法导论的书手撕过一遍，印象不是很深刻，容易忘记！好记性不如烂笔头！多自己思考解决问题

1,交换类CAS【最简单】

　　稳定，n^2

　　1.1冒泡法【①普通冒泡；②鸡尾酒法】

package com.cnblogs.mufasa.demo1_CAS;import org.junit.Test;public class Solution1_bubble {    //1，普通冒泡，由左及右一遍遍来刷，时间复杂度O(n^2)
    public void normal_Bubble(int[] nums){//默认直接，小到大
        int len=nums.length;
        for(int i=0;i<len-1;i++){
            for(int j=0;j<len-i-1;j++){
                if(nums[j]>nums[j+1]){
                    int temp=nums[j+1];
                    nums[j+1]=nums[j];
                    nums[j]=temp;
                }
            }
        }
    }    //2，鸡尾酒冒泡，左右左右变换,时间复杂度O(n^2)但是理论上更加优化
    public void cocktail_Bubble(int[] nums) {
        int len = nums.length;
        int x=0,y=len-1;
        while (x<y){
            for(int i=x;i<y;i++){
                if(nums[i]>nums[i+1]){
                    int temp=nums[i+1];
                    nums[i+1]=nums[i];
                    nums[i]=temp;
                }
            }
            y--;
            for(int i=y;i>0;i--){
                if(nums[i]<nums[i-1]){
                    int temp=nums[i-1];
                    nums[i-1]=nums[i];
                    nums[i]=temp;
                }
            }
        }
    }    public void printOut(int[] nums){
//        int len=nums.length;
        for(int temp:nums){
            System.out.print(temp+",");
        }
        System.out.println();
    }    @Test
    public void test(){
        int[] nums={5,14,478,6,41,698,14,5,3};
        printOut(nums);//        normal_Bubble(nums);
        cocktail_Bubble(nums);
        printOut(nums);    }}

图-普通冒泡排序

图-鸡尾酒排序

　　1.2快速排序【①单边循环快排；②双边循环快排】

　　CAS排序的一种，时间复杂度平均为O(nlogn)，最坏为O(n^2)

　　Arrays.sort()底层就是使用双轴快排实现的 https://blog.csdn.net/github_38838414/article/details/80642329

package com.cnblogs.mufasa.demo1_CAS;import org.junit.Test;public class Solution2_quick {    //1，单边循环法，快排
    public void quick_sort1(int[] nums){
        sin_Quick1(nums,0, nums.length-1);//前闭后闭
    }    private void sin_Quick1(int[] nums,int x,int y) {
        if (y - x == 1) {
            if (nums[x] > nums[y]) {
                int temp = nums[x];
                nums[x] = nums[y];
                nums[y] = temp;
            }
            return;
        } else if (x >= y) {
            return;
        }        int mark=x,povit=nums[x];
        for(int i=x;i<=y;i++){
            if(nums[i]<povit){
                mark++;
                int temp=nums[i];
                nums[i]=nums[mark];
                nums[mark]=temp;
            }
        }
        int temp=nums[mark];
        nums[mark]=nums[x];
        nums[x]=temp;        sin_Quick1( nums, x, mark-1);
        sin_Quick1( nums, mark+1, y);
    }    //2，双边循环法，快排
    public void quick_sort2(int[] nums){
        sin_Quick2(nums,0, nums.length-1);//前闭后闭
    }    private void sin_Quick2(int[] nums,int x,int y){
        if(y-x==1){
            if(nums[x]>nums[y]){
                int temp=nums[x];
                nums[x]=nums[y];
                nums[y]=temp;
            }
            return;
        }else if(x>=y){
            return;
        }        int pivot=nums[x];
        int left=x,right=y;
        boolean flag=true;        while (left<right){
            if(flag){
                if(pivot<=nums[right]){
                    right--;
                }else {
                    flag=false;
                }
            }else {
                if(nums[left]<=pivot){
                    left++;
                }else {
                    int temp=nums[left];
                    nums[left]=nums[right];
                    nums[right]=temp;
                    flag=true;
                    right--;
                }
            }
        }
        int temp=nums[left];
        nums[left]=nums[x];
        nums[x]=temp;
        sin_Quick2(nums,x,left-1);
        sin_Quick2(nums,left+1,y);
    }    public void printOut(int[] nums){
        for(int temp:nums){
            System.out.print(temp+",");
        }
        System.out.println();
    }    @Test
    public void test(){
        int[] nums={13,14,478,6,41,698,12,5,3};
//        int[] nums={5,2,9,6,1,0,3,7,8};
        printOut(nums);        quick_sort1(nums);
//        quick_sort2(nums);
        printOut(nums);
    }
}

图-快速排序

2，选择排序【最简单】

　　原理：每次选择极值往同一个方向推过去，有点像这样：我们在垃圾堆里找值钱的物件，每次找最值钱的那一件丢到我们的蛇皮袋子中，下一次在剩余的垃圾中找最值钱的物件，再次丢到我们的宝贝蛇皮袋子里，依次循环，那么最后我们完成地球清洁工作后，我们的蛇皮袋子里的垃圾价值由下到上价值依次递增！！！这个就是普通的选择排序！！！不稳定，n^2；不稳定的原因：由小到大排序下面的数组[6,6,1]

　　堆排序，利用了堆这种数据结构的特性来辅助完成排序工作，时间复杂度为O(nlogn)，需要开辟额外空间【其实我们不开辟额外空间也可以，把原始数组空间直接利用当做堆的内存空间来用，之后出堆的时候前面出，后面进】

package com.cnblogs.mufasa.demo2_select;import org.junit.Test;import java.util.PriorityQueue;public class Solution1_select {
    private static final int MAX=Integer.MAX_VALUE;    //1，普通选择排序，时间复杂度为O(n^2)
    public void normal_select1(int[] nums){
        int len=nums.length,min,loc;
        for(int i=0;i<len;i++){
            min=MAX;
            loc=i;
            for(int j=i;j<len;j++){
                if(nums[j]<min){
                    min=nums[j];
                    loc=j;
                }
            }
            nums[loc]=nums[i];
            nums[i]=min;
        }
    }    //2，利用最大堆、最小堆特性进行排序【Java容器中的优先队列就是使用的堆元素】
    public void normal_select2(int[] nums){
        int len=nums.length;
        PriorityQueue<Integer> queue=new PriorityQueue<>(len);
        for(int temp:nums){
            queue.add(temp);
        }
        for(int i=0;i<len;i++){
            nums[i]=queue.poll();
        }
    }    //3，数据结构堆的手动实现
    public void normal_select3(int[] nums) throws Exception {
        Heap heap=new Heap(false);
        for(int temp:nums){
            heap.add(temp);
        }
        for(int i=nums.length-1;i>=0;i--){
            nums[i]=heap.poll();
        }
    }    public void printOut(int[] nums){
        for(int temp:nums){
            System.out.print(temp+",");
        }
        System.out.println();
    }    @Test
    public void test() throws Exception {
        int[] nums={13,14,478,6,41,698,12,5,3};
//        int[] nums={5,2,9,6,1,0,3,7,8};
        printOut(nums);//        normal_select1(nums);
//        normal_select2(nums);
        normal_select3(nums);
        printOut(nums);
    }
}

数据结构-堆 Heap.java

package com.cnblogs.mufasa.demo2_select;public class Heap {
    private static final int CAPACITY=16;
    private static final boolean TYPE=true;    private static int[] nums;
    private int capacity=16;
    int size=0;    private boolean type=true;//true由小到大，false由大到小
    public Heap(){
        this(CAPACITY);
    }    public Heap(int capacity){
        this(capacity,TYPE);
    }    public Heap(boolean type){
        this(CAPACITY,type);
    }    public Heap(int capacity,boolean type){
        this.capacity=capacity;
        this.type=type;
        nums=new int[capacity];
    }    //数据添加
    public void add(int num){
        if(size+1>=capacity){
            dilatate();
        }
        nums[size+1]=num;
        reSortUp(size+1);
        size++;
    }    private void reSortUp(int index){
        if(type){//由小到大
            while (index!=1){
                if(nums[index/2]>nums[index]){
                    int temp=nums[index];
                    nums[index]=nums[index/2];
                    nums[index/2]=temp;
                    index/=2;
                }else if(nums[index/2]==nums[index]){
//                    throw new IllegalArgumentException("数据结构-堆不接受重复数据输入");
                    break;
                }else {
                    return;
                }
            }
        }else {//由大到小
            while (index!=1){
                if(nums[index/2]<nums[index]){
                    int temp=nums[index];
                    nums[index]=nums[index/2];
                    nums[index/2]=temp;
                    index/=2;
                }else if(nums[index/2]==nums[index]){
//                    throw new IllegalArgumentException("数据结构-堆不接受重复数据输入");
                    break;
                }else {
                    return;
                }
            }
        }
    }    //数据输出，并且清楚该数据
    public int poll() throws Exception {
        if(size>0){
            int temp=nums[1];
            nums[1]=nums[size];
            reSortDown();
            size--;
            return temp;
        }else {
            throw new Exception("数据为空");
        }
    }    private void reSortDown(){
        int index=1;
        int L,R;
        if(type){//由小到大
            while (index<size){
                L=index*2;
                R=L+1;
                if(R<=size){
                    boolean flag=nums[L]<nums[R];
                    int min=(flag?nums[L]:nums[R]);
                    if(nums[index]>min){
                        if(flag){
                            int temp=nums[index];
                            nums[index]=nums[L];
                            nums[L]=temp;
                            index=L;
                        }else {
                            int temp=nums[index];
                            nums[index]=nums[R];
                            nums[R]=temp;
                            index=R;
                        }
                    }else {
                        return;
                    }
                }else if(L<=size){
                    if(nums[index]>nums[L]){
                        int temp=nums[index];
                        nums[index]=nums[L];
                        nums[L]=temp;
                    }
                    return;
                }else {
                    return;
                }
            }
        }else {//由大到小
            while (index<size){
                L=index*2;
                R=L+1;
                if(R<size){
                    boolean flag=nums[L]<nums[R];
                    int max=(flag?nums[R]:nums[L]);
                    if(nums[index]<max){
                        if(flag){
                            int temp=nums[index];
                            nums[index]=nums[R];
                            nums[R]=temp;
                            index=R;
                        }else {
                            int temp=nums[index];
                            nums[index]=nums[L];
                            nums[L]=temp;
                            index=L;
                        }
                    }else {
                        return;
                    }
                }else if(L<size){
                    if(nums[index]<nums[L]){
                        int temp=nums[index];
                        nums[index]=nums[L];
                        nums[L]=temp;
                    }
                    return;
                }else {
                    return;
                }
            }
        }
    }    //数据输出，不清除该数据
    public int peek() throws Exception {
        if(size>0){
            return nums[0];
        }else {
            throw new Exception("数据为空");
        }
    }    //数据扩容,二倍扩容
    private void dilatate(){
        capacity=capacity<<1;
        int[] pre=new int[capacity];
        for(int i=1;i<=size;i++){
            pre[i]=nums[i];
        }
        nums=pre;
    }}class Client{
    public static void main(String[] args) throws Exception {
        Heap heap=new Heap(4,true);
//        Heap heap=new Heap(4,false);
        heap.add(5);
        heap.add(3);
        heap.add(3);
        heap.add(7);
        heap.add(1);
        heap.add(0);
        heap.add(8);
        heap.add(8);        int len=heap.size;
        for(int i=0;i<len;i++){
            System.out.print(heap.poll()+",");
        }
    }
}
/*
0,1,3,5,7,8,
8,7,5,3,1,0,
 */

图-普通选择排序

3,插入排序【简单】

　　稳定,n^2、希尔有点麻烦，但是理解其本质就很简单了

package com.cnblogs.mufasa.demo3_insert;import org.junit.Test;public class Solution1_insert {    //1，普通插入排序,时间复杂度O(n^2)
    public void normal_insert1(int[] nums){
        int len=nums.length;
        for(int i=1;i<len;i++){
            sinInsert(nums,i);
        }
    }    private void sinInsert(int[] nums,int loc){
        for(int i=loc-1;i>=0;i--){
            if(nums[i]<=nums[loc]){
                break;
            }else {
                int temp=nums[i];
                nums[i]=nums[loc];
                nums[loc]=temp;
                loc--;
            }
        }
    }    //2，希尔排序，多路进行并发排序，时间复杂度为O(n^1.3)
    //只要是利用了分治并发的操作，后期可以在Java并发学习中将这个进行知识整合，bingo
    public void shell_insert2(int[] nums){
        int len=nums.length;
        int step=len/2;
        while (step!=0){            for(int i=0;i<step;i++){
                sinShellInsert1(nums,i,len, step);
            }
            step/=2;
        }
    }    //2.1希尔排序的一级功能
    private void sinShellInsert1(int[] nums,int x,int len, int step){
        x+=step;
        while(x<len){
            sinShellInsert2(nums,x,step);
            x+=step;
        }
    }    //2.2希尔排序的二级功能
    private void sinShellInsert2(int[] nums,int x, int step){
        while (x>=step){
            if(nums[x-step]<=nums[x]){
                break;
            }else {
                int temp=nums[x];
                nums[x]=nums[x-step];
                nums[x-step]=temp;
                x-=step;
            }
        }
    }    public void printOut(int[] nums){
        for(int temp:nums){
            System.out.print(temp+",");
        }
        System.out.println();
    }    @Test
    public void test(){
//        int[] nums={13,14,478,6,41,698,12,5,3};
        int[] nums={5,2,9,6,1,0,3,7,8};
        printOut(nums);//        normal_insert1(nums);
        shell_insert2(nums);
        printOut(nums);
    }
}

图-普通插入排序

图-希尔插入排序

4，归并排序【中等难度吧！还是有点难度吧】

第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置重复步骤3直到某一指针超出序列尾将另一序列剩下的所有元素直接复制到合并序列尾

package com.cnblogs.mufasa.demo4_merge;import org.junit.Test;public class Solution {
    static int[] arr;
    //1,由小往大归并，2-4-8，将小份问题组合成大份问题
    public void merge_sort1(int[] nums){
        int len=nums.length;
        arr=new int[len];
        sort1(nums,len,1);
    }    private void sort1(int[] nums,int len,int step){
        int L1=0,mid=step-1,R=mid+step;
        int addNum=2*step;
        while (mid<len-1){
            if(R<len){
                merge(nums,L1,mid,R);
            }else {
                merge(nums,L1,mid,len-1);
            }
            mid+=addNum;
            L1+=addNum;
            R+=addNum;
        }
        if(step<len){
            sort1(nums,len,step*2);
        }
    }    //2，由大往小归并，8-4-2【本质上还是一样，不过将问题由大拆分成小的】
    public void merge_sort2(int[] nums){
        arr=new int[nums.length];
        sort2(nums, 0, nums.length-1);
    }    //有点类似于二叉树的后续遍历coding
    private void sort2(int[] nums,int L,int R){//左闭右开
        if (L == R) {
            return;
        }
        int mid=(L+R)>>1;
        sort2(nums,L,mid);
        sort2(nums,mid+1,R);
        merge(nums,L,mid,R);
    }    private void merge(int[] nums,int L,int mid,int R){
        int i = L;
        int p1 = L;
        int p2 = mid + 1;        while(p1 <= mid && p2 <= R) {
            arr[i++] = nums[p1] < nums[p2] ? nums[p1++] : nums[p2++];
        }
        while(p1 <= mid) {
            arr[i++] = nums[p1++];
        }
        while(p2 <= R) {
            arr[i++] = nums[p2++];
        }        for(i = L; i <= R; i++) {
            nums[i] = arr[i];
        }    }    public void printOut(int[] nums){
        for(int temp:nums){
            System.out.print(temp+",");
        }
        System.out.println();
    }    @Test
    public void test(){
//        int[] nums={13,14,478,6,41,698,12,5,3};
        int[] nums={5,2,9,6,1,0,3,7,8};
        printOut(nums);        merge_sort1(nums);
//        merge_sort2(nums);
        printOut(nums);
    }
}

图-归并排序

5，分割线小结

　　上述的冒泡排序、选择排序、插入排序、归并排序都是属于比较类排序，他们大多数不需要开辟额外地址空间，时间复杂度大致范围为O(N^2)~O(nlogn)，其中希尔排序的时间复杂度为O(n^1.3)

　　下面将要给大家介绍的是另外一类排序方法，非比较类排序！！！他们的时间复杂度可以降的很低，但是代价是要开辟额外的内存空间。

6，计数排序【简单】

　　算法复杂度O（n+k）

　　本质就是通过各个数值的个数，其中有个键值对——键为这个数值大小，值为其在原始数组中的个数；由键的大小及其个数进行数组还原。

package com.cnblogs.mufasa.demo5_count;import org.junit.Test;import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;public class Solution {    //1,计数排序，原理很简单，统计个数，还原！！！简单粗暴
    //这里直接使用TreeMap实现的
    public void count_sort1(int[] nums){
        TreeMap<Integer,Integer> hm=new TreeMap<>();
        for(int n:nums){
            Object temp=hm.get(n);
            if(temp==null){
                hm.put(n,1);
            }else {
                hm.put(n,(Integer)temp+1);
            }
        }
        int loc=0;
        for(Map.Entry<Integer,Integer> entry:hm.entrySet()){
            for(int i=0;i<entry.getValue();i++){
                nums[loc]=entry.getKey();
                loc++;
            }
        }
    }    //2，直接判断最大的数值是多少来进行数组存储
    public void count_sort2(int[] nums){
        int[] cnts=new int[findMax(nums)+1];
        for(int temp:nums){
            cnts[temp]++;
        }
        int loc=0;
        for(int i=0;i<cnts.length;i++){
            for(int j=0;j<cnts[i];j++){
                nums[loc]=i;
                loc++;
            }
        }
    }    private int findMax(int[] nums){
        int max=Integer.MIN_VALUE;
        for(int temp:nums){
            if(temp>max) max=temp;
        }
        return max;
    }    public void printOut(int[] nums){
        for(int temp:nums){
            System.out.print(temp+",");
        }
        System.out.println();
    }    @Test
    public void test(){
//        int[] nums={13,14,478,6,41,698,12,5,3};
        int[] nums={13,14,478,6,41,698,12,5,3,12,13,400,12};
//        int[] nums={5,2,9,6,1,0,3,7,8};
        printOut(nums);//        count_sort1(nums);
        count_sort2(nums);
        printOut(nums);
    }
}

图-计数排序

7，桶排序【简单】

　　这个和计数排序有点相似，虽然不是统计个数，但是他把各个位【十位、百位】分桶丢进不同的bucket中？！垃圾分类，不同的垃圾先进行大类划分，之后在进行小类的划分。

package com.cnblogs.mufasa.demo6_bucket;import org.junit.Test;public class Solution {
    static class Linked{
        int value;
        Linked pre;
        Linked next;
        public Linked(int value){
            this.value=value;
        }
        public void insert(Linked node,int value){
            if(value<node.value){
                if(next==null){
                    next=new Linked(node.value);
                    node.next.pre=node;
                    node.value=value;
                }else {
                    Linked newNode=new Linked(node.value);
                    newNode.next=node.next;
                    node.next.pre=newNode;
                    node.value=value;
                    node.next=newNode;
                    newNode.pre=node;
                }
            }else {
                if(node.next==null){
                    node.next=new Linked(value);
                    node.next.pre=node;
                }else {
                    insert(node.next,value);
                }
            }
        }
    }    public void bucket_sort1(int[] nums){
        Linked[] linkeds=new Linked[10];
        for(int temp:nums){
            int highN=temp/10;
            if(linkeds[highN]==null){
                linkeds[highN]=new Linked(temp);
            }else {
                linkeds[highN].insert(linkeds[highN],temp);
            }
        }
        int loc=0;
        for(Linked linked:linkeds){
            Linked preNode=linked;
            while (preNode!=null){
                nums[loc]=preNode.value;
                loc++;
                preNode=preNode.next;
            }
        }
    }    public void printOut(int[] nums){
        for(int temp:nums){
            System.out.print(temp+",");
        }
        System.out.println();
    }    @Test
    public void test(){
        int[] nums={13,14,47,6,41,69,12,5,3};
//        int[] nums={5,2,9,6,1,0,3,7,8};
//        int[] nums={5,2,9,6,1,0,3,7,8,};
        printOut(nums);        bucket_sort1(nums);
//        quick_sort2(nums);
        printOut(nums);
    }
}

图-桶排序

8，基数排序【简单】

　　需要使用到队列数据结构！把个位十位….就和垃圾分类一样逐个丢进对应的队列，全部丢进去之后在逐个出队，还原反复多次【取决于最大值的位数】

package com.cnblogs.mufasa.demo7_radix;import org.junit.Test;import java.util.LinkedList;
import java.util.Queue;public class Solution {
    static class Node{
        int value;
        public Node(int value){
            this.value=value;
        }
    }    static class myRadixBucket<Node>{
        LinkedList<Node> [] queues=new LinkedList[10];
        public myRadixBucket(){
            for(int i=0;i<10;i++){
                queues[i]=new LinkedList<>();
            }
        }
        public LinkedList<Node>[] getInstance(){
            return queues;
        }
    }    public void radix_sort1(int[] nums,int loop){
        myRadixBucket mr=new myRadixBucket();
        LinkedList<Node> [] queues=mr.getInstance();//需要用到队列        for(int i=0;i<loop;i++){
            int loc1=(int) Math.pow(10,i);
            for(int temp:nums){
                queues[temp/loc1%10].add(new Node(temp));
            }
            int loc=0;
            for(Queue<Node> queue:queues){
                int len=queue.size();
                Node preNode;
                for(int j=0;j<len;j++){
                    preNode=queue.poll();
                    nums[loc]=preNode.value;
                    loc++;
                }
            }
        }
    }    public void printOut(int[] nums){
        for(int temp:nums){
            System.out.print(temp+",");
        }
        System.out.println();
    }    @Test
    public void test(){
        int[] nums={13,14,678,6,41,498,12,5,3};
//        int[] nums={5,2,9,6,1,0,3,7,8};
        printOut(nums);        radix_sort1(nums,3);//这里的loop与原始数组中最大数值的位长度相等，这里的原始数据最大值为678为百位取值loop=3
//        quick_sort2(nums);
        printOut(nums);
    }
}/*
41,12,13,3,14,5,6,678,498,  【第一次，基数排序】
3,5,6,12,13,14,41,678,498,  【第二次，基数排序】
3,5,6,12,13,14,41,498,678,  【第三次，基数排序】
注意每一次都是进行了每个位【个位、十位、百位】上的有序整理
 */

图-基数排序

后面附上我之前使用Python写的排序算法汇总：十大经典排序算法（python实现）（原创）