博主主页: 码农派大星.

    数据结构专栏:Java数据结构

 数据库专栏:MySQL数据库

关注博主带你了解更多数据结构知识

---

1.冒泡排序

private static void swap(int[] arrary,int i,int j){
        int tmp = arrary[i];
        arrary[i] = arrary[j];
        arrary[j] = tmp;

public static void  bubbleSort(int[] arrary){
        for (int i = 0; i <arrary.length-1 ; i++) {
            for (int j = 0; j < arrary.length-1-i; j++) {
                if(arrary[j]> arrary[j+1]){
                    swap(arrary,j,j+1);
                }

            }
        }
        return arrary;
    }

冒泡排序总结

1. 冒泡排序是一种非常容易理解的排序

2. 时间复杂度：O(N^2)

3. 空间复杂度：O(1)

4. 稳定性：稳定 

2.快速排序

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元 素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有 元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

1.Hoare版

public static void  quickSort(int[] arrary){
        quick(arrary,0,arrary.length-1);
        return arrary;

    }
    private static void swap(int[] arrary,int i,int j){
        int tmp = arrary[i];
        arrary[i] = arrary[j];
        arrary[j] = tmp;
    private static void quick(int [] arrary,int start,int end){
        if (start >= end) {
            return;
        }
        int par = partition(arrary,start,end);
        quick(arrary,start,par-1);
        quick(arrary,par+1,end);
    }
    private static int partition(int [] arrary,int left,int right){
        int i = left;
        int tmp = arrary[left];
        while (left < right){
            //right-- : 先走左边会导致最后相遇的地方比基准大的数据,
            // 交换完后,会把大于基准的值换到前面
            while (left < right && arrary[right] >= tmp){
                right--;
            }
            while (left < right && arrary[left] <= tmp){
                left++;
            }
            swap(arrary,left,right);
        }
        //此时相遇left=right;
        swap(arrary,left,i);
        return right;
    }

2.挖坑法 

public static void  quickSort(int[] arrary){
        quick(arrary,0,arrary.length-1);
        return arrary;

    }
private static void quick(int [] arrary,int start,int end){
        if (start >= end) {
            return;
        }
        int par = partitionWaken(arrary,start,end);
        quick(arrary,start,par-1);
        quick(arrary,par+1,end);
    }
private static int partitionWaken(int [] arrary,int left,int right){
        int tmp = arrary[left];
        while (left<right){
            while (left < right && arrary[right] >= tmp){
                right--;
            }
            arrary[left] = arrary [right];
            while (left<right && arrary[left] <= tmp){
                left++;
            }
            arrary[right] = arrary[left];
        }
        arrary[left] = tmp;
        return left;
    }

3.快速排序优化

1. 三数取中法选key

 public static void  quickSort(int[] arrary){
        quick(arrary,0,arrary.length-1);
return arrary;

    }
    private static void quick(int [] arrary,int start,int end){
        if (start >= end) {
            return;
        }

        int index = midThreeNum(arrary,start,end);
        swap(arrary,index,start);

        int par = partitionWaken(arrary,start,end);
        quick(arrary,start,par-1);
        quick(arrary,par+1,end);
    }

private static int partitionWaken(int [] arrary,int left,int right){
        int tmp = arrary[left];
        while (left<right){
            while (left < right && arrary[right] >= tmp){
                right--;
            }
            arrary[left] = arrary [right];
            while (left<right && arrary[left] <= tmp){
                left++;
            }
            arrary[right] = arrary[left];
        }
        arrary[left] = tmp;
        return left;
    }
    private static int midThreeNum(int [] arrary,int left,int right){
        int mid = (left+right)/2;
        if (arrary[left] < arrary[right]){
            if (arrary[mid] < arrary[left]) {
                return left;

            }else if (arrary[mid] > arrary[right]){
                return right;
            }else {
                return mid;
            }
        }else{
            if (arrary[mid] < arrary[right]){
                return right;
            }else if(arrary[mid] > arrary[left]){
                return left;
            }else {
                return mid;
            }
        }
    }

2. 递归到小的子区间时，可以考虑使用插入排序

我们在数组中数据小于等于10时改为插入排序,提高了排序的效率.

 public static void  quickSort(int[] arrary){
        quick(arrary,0,arrary.length-1);
return arrary;

    }
    private static void quick(int [] arrary,int start,int end){
        if (start >= end) {
            return;
        }
        if (end - start + 1 <= 10) {
            inserSortRange(arrary,start,end);
            return;
        }

        int index = midThreeNum(arrary,start,end);
        swap(arrary,index,start);

        int par = partitionWaken(arrary,start,end);
        quick(arrary,start,par-1);
        quick(arrary,par+1,end);
    }
    public static  void inserSortRange(int [] array,int left,int right){
        for(int i = left+1; i< right;i++){
            int tmp = array[i];
            int j = i-1;
            for (; j >=0 ; j--) {
                if (array[j] > tmp) {
                    array[j+1] = array[j];
                }else {
                    //array[j+1]= tmp;
                    break;
                }
            }
            array[j+1]= tmp;
        }
    }
 private static int partitionWaken(int [] arrary,int left,int right){
        int tmp = arrary[left];
        while (left<right){
            while (left < right && arrary[right] >= tmp){
                right--;
            }
            arrary[left] = arrary [right];
            while (left<right && arrary[left] <= tmp){
                left++;
            }
            arrary[right] = arrary[left];
        }
        arrary[left] = tmp;
        return left;
    }
    private static int midThreeNum(int [] arrary,int left,int right){
        int mid = (left+right)/2;
        if (arrary[left] < arrary[right]){
            if (arrary[mid] < arrary[left]) {
                return left;

            }else if (arrary[mid] > arrary[right]){
                return right;
            }else {
                return mid;
            }
        }else{
            if (arrary[mid] < arrary[right]){
                return right;
            }else if(arrary[mid] > arrary[left]){
                return left;
            }else {
                return mid;
            }
        }
    }

4.非递归的快速排序 

//非递归快速排序
 
    public static void quickNot(int[] array){
        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = array.length - 1;
        int par = partition(array,left,right);
        if (par > left+1){
            stack.push(left);
            stack.push(par-1);

        }
        if (par < right-1){
            stack.push(par+1);
            stack.push(right);
        }
        while (!stack.isEmpty()){
            right = stack.pop();
            left = stack.pop();
            par = partitionWaken(array,left,right);
            if(par > left+1){
                stack.push(left);
                stack.push(par-1);
            }
            if (par < right -1){
                stack.push(par+1);
                stack.push(right);
            }
        }
         return array;
    }
private static int partition(int [] arrary,int left,int right){
        int i = left;
        int tmp = arrary[left];
        while (left < right){
            //right-- : 先走左边会导致最后相遇的地方比基准大的数据,
            // 交换完后,会把大于基准的值换到前面
            while (left < right && arrary[right] >= tmp){
                right--;
            }
            while (left < right && arrary[left] <= tmp){
                left++;
            }
            swap(arrary,left,right);
        }
        //此时相遇left=right;
        swap(arrary,left,i);
        return right;
    }

未优化的快速排序,再遇到数据过多时,程序会崩. 

1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序

2. 时间复杂度：O(N*logN)

快速排序和堆排序时间复杂度一样,但是快速排序要比堆排序快

3. 空间复杂度：O(logN)

4. 稳定性：不稳定