常用Java排序算法

川长思鸟来 2022-08-07 07:44 244阅读 0赞

## 时间复杂度 ##

f(n) 算法基本操作执行的方法  
n表示算法的规模  
O(n) f(n)的量级  
稳定性： 同样元素的相对位置在排序前后是否有可能发生变化

## 冒泡排序 ##

### 普冒 ###

public class SortUtil {
        public static SortService bubble = new BubbleSort();
        public static SortService bubbleA = new BubbleASort();
    
        public static void main(String[] args) {
            int[] data = new int[10000];
            for (int i = 0; i < data.length; i++) {
                data[i] = new Random().nextInt(50000);
            }
    
            SortUtil.sort(SortUtil.bubbleA, data);
            System.out.println(Arrays.toString(data));
        }
    
        private static void sort(SortService sortService, int[] data) {
            long before = System.currentTimeMillis();
            sortService.sort(data);
            long after = System.currentTimeMillis();
            System.out.println(sortService.getName() + "cost:" + (after - before));
        }
    }
    
    interface SortService{
        public void sort(int[] data);
    
        public String getName();
    }
    
    class BubbleSort implements SortService{
        @Override
        public void sort(int[] data) {
            for (int i = 0; i < data.length; i++) {  // n
                for (int j = 0; j < data.length - 1 - i; j++) {   // n(n-1)/2
                    if(data[j] > data[j + 1]){    // n(n-1)/2
                        int temp = data[j + 1];   // n(n-1)/2
                        data[j + 1] = data[j];    // n(n-1)/2
                        data[j] = temp;           // n(n-1)/2
                    }
                }
            }
        }
    
        @Override
        public String getName() {
            return "冒泡排序";
        }
    }

*  耗时：170
 *  时间复杂度： 最大：f(n) = n + 5\*n(n-1)/2 ;O(n)=n^2 最小 f(n) = n + n(n-1)/2, O(n^2)
 *  稳定

### 改进冒 ###

上面的冒泡有个问题，是完全正序是复杂度过大。可以优化成如下：

class BubbleASort implements SortService { 
    
        @Override
        public void sort(int[] data) {
            boolean swap = true;
            for (int i = 0; i < data.length; i++) {  // 2
                if(! swap){   // 2
                    break;
                }
                swap = false; // 1
                for (int j = 0; j < data.length - 1 - i; j++) {  // n
                    if(data[j] > data[j + 1]){   // n
                        int temp = data[j + 1];
                        data[j + 1] = data[j];
                        data[j] = temp;
                        swap = true;
                    }
                }
            }
        }
    
        @Override
        public String getName() {
            return "冒泡排序-改";
        }
    }

*  耗时：会比上面慢一点
 *  时间复杂度：最大差不多， 最小: f(n) = 2n + 2 + 2 + 1; O(n)
 *  稳定

## 选择排序 ##

/** * 选择排序 * 把数组分割为有序区和无序区 * 从无序区中[选择出]最小/最大的放到有序区的最后 */
    class SelectSort implements SortService{
    
        @Override
        public void sort(int[] data) {
            for (int i = 0; i < data.length; i++) {   //n
                // 选择最小数的位置的下标
                int minIndex = i;                     // n
                for (int j = i + 1; j < data.length; j++) {  // n(n-1)/2
                    if(data[j] < data[minIndex]){    // n(n-1)/2 
                        minIndex = j;              // n(n-1)/2
                    }
                }
                int temp = data[i];                //n
                data[i] = data[minIndex];          //n
                data[minIndex] = temp;             //n
            }
        }
    
        @Override
        public String getName() {
            return "选择排序";
        }
    }

*  耗时： 70 比冒泡快不少，是因为减少了数据交换的执行测试
 *  时间复杂度：最坏和平均： f(n)=5n + 3n(n-1)/2 O(n^2). 最好的情况同样跟冒泡一样需要加入检测交换的情况，加入之后其复杂度为 O(n)】
 *  不稳定

## 插入排序 ##

### 普插 ###

/** * 插入排序 * 把数组分为左有序，右无序，初始状态左第一个为有序，后面都为无序 * 遍历无序集合，从第一个元素开始，跟有序的所有比较，找到合适位置 * 从这个位置，左部元素右移该位置插入无序集合中遍历的这个元素 */
    class InsertSort implements  SortService{
    
        @Override
        public void sort(int[] data) {
            for (int i = 1; i < data.length; i++) {   //n
                int j;                                //n
                for (j = i - 1; j >= 0; j--) {  //n(n-1)/2 因为左有序，因此找到了data[i]大于的第一个位置，就说明data[i]应该插在这个位置之后
                    if(data[j] < data[i]){      //n(n-1)/2，
                        break;
                    }
                }
                // 插入元素并后移
                if(j != (i-1)){                 // n
                    int temp = data[i];         // n
                    for (int k = i - 1; k > j; k--) {  // n(n-1)/2
                        data[k + 1] = data[k];         // n(n-1)/2
                    }
                    data[j + 1] = temp;                // n
                }
            }
        }
    
        @Override
        public String getName() {
            return "插入排序";
        }
    }

*  稳定
 *  耗时 63， 比选择好，是因为平均复杂度低一点，但是最坏情况比选择还要高
 *  复杂度：最坏f(n)=5n + 2n(n-1) O(n^2) 平均 O(n) 最好的情况：f(n)=4n O(n)

### 插入排序-改 ###

/** * 插入排序-该 * 改前是先找插入位置，然后统一移动顺序，再插入 * 改后，使用类似冒泡的方式，在比较的同时就移动顺序 */
    class InsertSortAdvance implements  SortService{
    
        @Override
        public void sort(int[] data) {
            for (int i = 1; i < data.length; i++) {     // n
                // j是有序表尾, 连带着无序表头做冒泡
                for (int j = i-1; j>=0 && data[j] > data[j+1]; j--) {       // 最坏n(n-1)/2 最好 // n
                    int temp = data[j];                                     // 最坏n(n-1)/2
                    data[j] = data[j+1];                                    // 最坏n(n-1)/2
                    data[j+1] = temp;                                       // 最坏n(n-1)/2
                }
            }
        }
    
        @Override
        public String getName() {
            return "插入排序";
        }
    }

*  稳定
 *  53， 因为平均中交换的操作可能执行的比较少。
 *  时间复杂度 最坏：f(n) = 2n(n-1) + n O(n^2) 最好f(n)=2n O(n)

## 二叉树排序 ##

/** * 二叉树 * 先构造二叉树，构建好之后就是有序的 * 然后遍历二叉树 */
    class BinaryTreeSort implements SortService{
        class Data{
            int i = 0;
            int[] data;
            public Data(int[] data){
                this.data = data;
            }
            public void add(int j){
                data[i++] = j;
            }
        }
    
        class BinaryNode{
            int value;
            BinaryNode left;
            BinaryNode right;
            public BinaryNode(int value){
                this.value = value;
                this.left = null;
                this.right = null;
            }
    
            public void add(int value){
                if(value > this.value){
                    if(this.right != null){
                        this.right.add(value);
                    }else{
                        this.right = new BinaryNode(value);
                    }
                }else{
                    if(this.left != null){
                        this.left.add(value);
                    }else{
                        this.left = new BinaryNode(value);
                    }
                }
            }
    
            // 中序遍历
            public void iterator(Data d){
                if(this.left != null){
                    this.left.iterator(d);
                }
                if(this.right != null){
                    this.right.iterator(d);
                }
                d.add(this.value);
            }
        }
        @Override
        public void sort(int[] data) {
            BinaryNode n = new BinaryNode(data[0]);
            for (int i = 1; i < data.length; i++) {
                n.add(data[i]);
            }
            Data d = new Data(data);
            n.iterator(d);
        }
    
        @Override
        public String getName() {
            return "二叉树排序";
        }
    }

*  稳定
 *  cost 3
 *  时间复杂度f(n) ~= nlogn + logn O(nlogn)

## 快速排序 ##

/** * 快速排序 * 选取一个元素，比其小的放在左边，比其大的放到右边 * 对于数组就是用旳第一个元素，然后从后往前比较，找到第一个比他小的，然后交换，再从前往后比较找到第一个比它大的交换，直到前后会和，完成一次分组。然后再对每个小组重新进行快排分组 */
    class QuickSort implements SortService{
    
        @Override
        public void sort(int[] data) {
            quickSort(data, 0, data.length-1);
        }
    
        private void quickSort(int[] data, int low, int high) {
            if(low >= high){
                return;
            }
            int p = partition(data, low, high);
            quickSort(data, low, p-1);
            quickSort(data, p+1, high);
        }
    
        /** * 得到分界线 * @param data * @param low * @param high * @return */
        private int partition(int[] data, int low, int high) {
            boolean asc = false;
            while(low != high){
                if(asc){
                    if(data[low] > data[high]){
                        int temp = data[low];
                        data[low] = data[high];
                        data[high] = temp;
                        asc = !asc;
                    }else{
                        high --;
                    }
    
                }else{
                    if(data[low] > data[high]){
                        int temp = data[low];
                        data[low] = data[high];
                        data[high] = temp;
                        asc = !asc;
                    }else{
                        low ++;
                    }
                }
            }
            return low;
        }
    
        @Override
        public String getName() {
            return "快速排序";
        }
    }

*  不稳定
 *  cost 2
 *  时间复杂度 最大O(n^2) 平均O(nlogn) 最小O(nlogn)

## 归并排序 ##

/** * 归并排序 * 申请空间，使其大小为两个已排序数组之和 * 设定两个指针，起始位置为两个数组头 * 比较两个指针，选择相对小的元素放入合并空间，并移动指针到下一个位置。直到某一个指针到达末尾 * 把另一个数组的所有元素复制到合并数组的末尾 */
    class MergeSort implements SortService{ 
    
        @Override
        public void sort(int[] data) {
            mergeSort(data, 0, data.length - 1);
            int mid = data.length / 2;
            // leftPart is data[]
        }
    
        private void mergeSort(int[] data, int left, int right) {
            if(left >= right){
                // 说明是单数组了，因此不进行分解了
                return;
            }
            int center = (left + right)/2;
            // 分解数组为左右两部分，分别排序归并
            mergeSort(data, left, center);
            mergeSort(data, center+1, right);
            // 开始归并
            merge(data, left, center, center+1, right);
        }
    
        private void merge(int[] data, int oneSortLeft, int oneSortRight, int anotherLeft, int anotherRight){
            int begin = oneSortLeft;
            // 用缓存来存储排序后的数据
            int[] temp = new int[anotherRight + 1 - oneSortLeft];
            int index = 0;
            while((oneSortLeft <= oneSortRight) && (anotherLeft<=anotherRight)){
                if(data[oneSortLeft] < data[anotherLeft]){
                    temp[index] = data[oneSortLeft];
                    oneSortLeft ++;
                    index++;
                }else{
                    temp[index] = data[anotherLeft];
                    anotherLeft ++;
                    index++;
                }
            }
            if(oneSortLeft <= oneSortRight){
                for (int i = oneSortLeft; i <= oneSortRight; i++) {
                    temp[index] = data[i];
                    index ++;
                }
            }else{
                for (int i = anotherLeft; i <= anotherRight; i++) {
                    temp[index] = data[i];
                    index ++;
                }
            }
    
            for (int i = 0; i < temp.length; i++) {
                data[i + begin] = temp[i];
            }
        }
    
    
        @Override
        public String getName() {
            return "归并排序";
        }
    }

*  稳定
 *  cost 3比快排慢一点点
 *  时间复杂度O(nlogn)，平均最大最小都是这么多

## Arrays.sort ##

*  Java对Primitive（int，float等原型数据）数组采用快速排序，对Object对象数组采用归并排序。
 *  这样是因为很多情况下对象的稳定性很重要，比如已经按照学号拍好序，想按照成绩再排一下
 *  实现中快排和归并都采用递归方式，而在递归的底层，也就是递归到后面数组长度小于7时，直接使用冒泡排序，而不再递归下去。
 *  这时因为当n较小的时候比较次数已经不是开销的大头，递归涉及的方法调用的开销反而会凸显
 *  当数组中的元素个数较少时，源码中的阀值为7，采用的是插入排序。尽管插入排序的时间复杂度为0(n^2)，但是当数组元素较少时，插入排序优于快速排序，因为这时快速排序的递归操作影响性能。
 *  快排时比较好的划分了元，比如比较小时，去前中后三个点的中间值作为元。或者更多的踩点来获得元，避免最坏情况的发生