数据结构_排序总结

蔚落 2023-10-10 15:22 99阅读 0赞

**目录**

1.插入排序

2.希尔排序

3.选择排序

4.堆排序

5.冒泡排序

6.快速排序

7.归并排序

8.计数排序

--------------------

## 1.插入排序 ##

//插入排序
        /**
         * 时间复杂度：最坏 即逆序情况：O（N^2） 最好：即有序情况O（N）
         * 因此当数据不太多，且接近有序时，直接插入排序效率很高
         * 空间复杂度：随着问题规模的扩大并没有扩展空间，因此空间复杂度为O（1）
         * 稳定性：稳定
         * @param arr
         * @return
         */
        public static void insertSort(int[] arr){
            if(arr.length==0){
                return ;
            }
            int currentValue = 0;//存放当前需要比较插入的值
            for (int i = 0; i < arr.length-1; i++) {
                int preIndex = i;
                currentValue = arr[preIndex+1];
                while(preIndex >= 0 && arr[preIndex] > currentValue){
                    arr[preIndex+1] = arr[preIndex];
                    preIndex--;
                }
                //找到插入的位置
                arr[preIndex+1] = currentValue;
            }
        }
        public static void insertSort1(int[] array){
            for (int i = 1; i < array.length; i++) {
                int j = i-1;
                int tmp = array[i];
                for (; j >= 0 ; j--) {
                    if(array[j] > array[i]){
                        array[j+1] = array[j];
                    }
                    else{
                        break;
                    }
                }
                array[j+1] = tmp;
            }
        }

## 2.希尔排序 ##

//shell排序
    
        /**
         * 当增量大于1时，都是进行预排序，gap=1时进行直接插入排序
         * 也是对插入排序的优化
         * 时间复杂度为O（N^1.3）
         * @param arr
         */
        public void shellSort(int[] arr){
            int gap = arr.length;
            while(gap > 1){
                gap /= 2;
                shell(arr,gap);
            }
        }
        public static void shell(int[] arr,int gap){
    
            //这里换成i += gap也能排序，只是并没有完成预排序
            // 是因为无论预排序是几轮
            // 最后gap都会为1进行插入排序
            for (int i = gap; i < arr.length; i++) {
                int tmp = arr[i];
                int j = i-gap;
                for (; j >= 0 ; j-=gap) {
                    if(arr[j] > tmp){
                        arr[j+gap] = arr[j];
                    }
                    else{
                        break;
                    }
                }
                arr[j+gap] = tmp;
            }
        }

## 3.选择排序 ##

//选择排序
        /*
        时间复杂度：O（N^2）
         */
        public  static void selectSort(int[] array){
            int minIndex = 0;
            for (int i = 0; i < array.length; i++) {
                //最小值的下标
                minIndex = i;
                for (int j = i+1; j < array.length; j++) {
                    if(array[j] < array[i]){
                        //更新
                        minIndex = j;
                    }
                }
                //如果最小值下标存的还是i，则说明确实是最小值，没有进行下标的交换
                //当i != minIndex时，要进行交换i位置的值和min位置的值
                if(i != minIndex){
                    swap(array,minIndex,i);
                }
            }
        }
        //优化
        public static void selectSort1(int[] array){
            int left = 0;
            int right = array.length-1;
            while(left<right){
                int minIndex = left;
                int maxIndex = right;
                //每次交换完区间会更新
                for (int i = left+1; i <= right; i++) {
                    if(array[i] > array[maxIndex]){
                        maxIndex = i;
                    }
                    if(array[i] < array[minIndex]){
                        minIndex = i;
                    }
                }
                //交换
                swap(array,minIndex,left);
                //当maxIndex为left时，最小值会和left交换，最大值就被交换走了
                //因此最小值交换后，要更新最大值maxindex，才能将正确的最大值换到right处
    
                if(maxIndex == left){
                    maxIndex = minIndex;
                }
                swap(array,maxIndex,right);
                //更新
                left++;
                right--;
            }
        }
        //交换函数
        public static void swap(int[] array,int i,int j){
            int tmp = array[i];
            array[i] = array[j];
            array[j] = tmp;
        }

## 4.堆排序 ##

//堆排序
        //时间复杂度：N(n*log(2(N)))
        //空间复杂度O（1）
        //稳定性：不稳定
        public static void heapSort(int[] array){
            //建立大根堆
            creatBigheap(array);
            int end = array.length-1;
            while(end>0){
                swap(array,0,end);
                shiftDown(array,0,end);
                end--;
            }
    
        }
        private static void creatBigheap(int[] array){
            for (int parent = (array.length-1-1)/2; parent >=0 ; parent--) {
                shiftDown(array,parent,array.length);
            }
        }
        private static void shiftDown(int[] array,int parent,int len){
            int child = (2*parent)+1;
            while(child<len){
                if(child + 1 < len && array[child] < array[child+1]){
                    child++;
                }
                if(array[child] > array[parent]){
                    swap(array,parent,child);
                    parent = child;
                    child = (2*parent)+1;
                }else{
                    break;
                }
            }
        }

## 5.冒泡排序 ##

/**
         * 冒泡排序
         * 时间复杂度 不优化O（N^2）
         * 优化: O（N）
         * 空间复杂度 : O（N）
         * 稳定性: 稳定
         * @param array
         */
        public static void bubbleSort(int[] array){
            for (int i = 0; i < array.length-1; i++) {
                boolean flag = false;
                for (int j = 0; j < array.length-1-i; j++) {
                    if(array[j] > array[j+1]){
                        swap(array,j,j+1);
                        flag = true;
                    }
                }
                if(flag ==false){
                    break;
                }
            }
        }

## 6.快速排序 ##

/*
        快速排序
         */
    
        /**
         * 时间复杂度：O（N*log（N））
         * 空间复杂度：O（log（N））
         * 稳定性:不稳定
         * 当数据有序时，时间复杂度O（N^2）空间复杂度O（N）
         * @param array
         */
        public static void quickSort(int[] array){
            sort(array,0, array.length-1);
        }
        private static void sort(int[] array,int start,int end){
            //防止只有左子树或者右子树的情况
            if(start >= end){
                return;
            }
            int povit = partion(array,start,end);
            sort(array,start,povit-1);
            sort(array,povit+1,end);
        }
        private static int partion(int[] array,int left,int right){
            //记录原始位置下标，方便后面和povit位置交换
            int i = left;
            //寻找参考值
            int povit = array[i];
            while(left<right){
                /**
                 * 问题1：为什么先从right 向左找？
                 * 从右边开始找基准位置，是因为从左边开始找，左边先找到一个比array[left]大的数，然后右边
                 * 向左找，左右肯定相遇，这时候交换，会把比基准值大的数交换到基准位置左边，达不到二分的目的了
                 *
                 * 问题2：为什么左右数组值比较时要带等于号？
                 * 如果出现两边开始时值相同的情况，即左值不小于也不大于右值，两个循环都不会进去
                 * 只会完成左右值一直交换，死循环了
                 */
    
                while(left < right && array[left] <= array[right]){ //单独的循环，防止循环内一直到left>right，要加条件
                    right--;
                }
                while(left < right && array[left] >= array[right]){
                    left++;
                }
                //交换
                swap(array,left,right);
            }
            //交换povit到相遇的位置
            swap(array,left,i);
            return left;
        }
    
        //挖坑法找基准
        private static int paration1(int[] array,int left,int right){
            int povit = array[left];
            while(left<right){
                while (left < right && array[right] >= povit) {
                    right--;
                }
                array[left] = array[right];
                while(left < right && array[left] <= povit){
                    left++;
                }
                array[right] = array[left];
            }
            array[left] = povit;
            return left;
        }
        //前后指针找基准
        private static int paration2(int[] array,int left,int right){
            int prev = left;
            int cur = left+1;
            while(cur <= right){
                if(array[cur] < array[left] && array[++prev] != array[cur]){
                    swap(array,prev,cur);
                }
                cur++;
            }
            swap(array,prev,left);
            return prev;
        }
        /**
         * 一般情况下题目中所给到的都是挖坑法划分出来的序列
         * 如果不是，再尝试其他的两种方法划分出来的序列
         */
    //快速排序的优化1：
        /*
        当数据接近有序或有序的时候，快速排序的时间复杂度达到最大，空间复杂度也非常大了，可能会栈溢出
        使用三数取中法优化
    
        在找基准之前，解决划分不均匀的问题
         */
        private static void sort1(int[] array,int start,int end){
            //防止只有左子树或者右子树的情况
            if(start >= end){
                return;
            }
            //在找基准之前，解决划分不均匀的问题,将关键值改变为中间大小的值后，能解决单分支的情况
            int index = findMidValOfIndex(array,start,end);
            swap(array,start,index);
    
            int povit = partion(array,start,end);
            sort(array,start,povit-1);
            sort(array,povit+1,end);
        }
        /*
        找到中位数
         */
        private static int findMidValOfIndex(int[] array,int start,int end){
            int midIndex = (start+end)/2;
    
            if(array[start] < array[end]){
                if(array[midIndex] < array[start]) {
                    return start;
                } else if (array[end] < array[midIndex]) {
                    return end;
                }
                else {
                    return midIndex;
                }
            }
            else {
                if (array[midIndex] > array[start]){
                    return start;
                } else if (array[midIndex] < array[end]) {
                    return end;
                }
                else {
                    return midIndex;
                }
            }
        }
    //快速排序的优化2：
        /*
        当递归的区间很小的时候我们可以用插入排序，二叉树后几层节点数占总体节点数的大部分，
        递归次数最多也发生在后几层，往后也越来越有序，就不递归了。用插入排序
         */
        private static void sort2(int[] array,int start,int end){
            //防止只有左子树或者右子树的情况
            if(start >= end){
               return;
            }
            if(( end-start+1) <= 15){
            //插入排序减少后几层 的递归
                insertSort1(array,start,end);
            }
            //在找基准之前，解决划分不均匀的问题,将关键值改变为中间大小的值后，能解决单分支的情况
            int index = findMidValOfIndex(array,start,end);
            swap(array,start,index);
    
            int povit = partion(array,start,end);
            sort(array,start,povit-1);
            sort(array,povit+1,end);
        }
        public static void insertSort1(int[] array,int left,int right){
            for (int i = left+1; i <= right ; i++) {
                int j = i-1;
                int tmp = array[i];
                for (; j >= left ; j--) {
                    if(array[j] > array[i]){
                        array[j+1] = array[j];
                    }
                    else{
                        break;
                    }
                }
                array[j+1] = tmp;
            }
        }

## 7.归并排序 ##

//归并排序递归写法
        /*
        时间复杂度:O(n*log(n))
        空间复杂度:O(n)
        稳定性:稳定
        还有:插入 , 冒泡 , 归并
         */
        //1.递归
        public static void mergeSort(int[] array){
            mergeSortChild(array,0,array.length-1);
        }
        private static void  mergeSortChild(int[] array,int left,int right){
            if(left == right){
                return;
            }
            //分解
            int mid = (left+right)/2;
            mergeSortChild(array,left,mid);
            //先递归左边,当左边都递归完成,会返回一个array中放的是tmpArr的值
            //递归右边结束,array[i] = arrTmp[i] 又会从0开始赋值,是错误的.
            //array[i+left] = tmpArr[i];可以避免错误,左边left =0相当于没有调整,右边left改变,进行调整正确赋值
            mergeSortChild(array,mid+1,right);
            //合并
            merge(array,left,mid,right);
        }
    
        private static void merge(int[] array,int left,int mid,int right){
            int s1 = left;
            int e1 = mid;
            int s2 = mid+1;
            int e2 = right;
            int k = 0;//tmpArr下标
            int[] tmpArr = new int[right-left+1];
            while (s1 <= e1 && s2 <= e2){
                if(array[s1] <= array[s2]){
                    tmpArr[k] = array[s1];
                    k++;
                    s1++;
                }
                else {
                    tmpArr[k] = array[s2];
                    k++;
                    s2++;
                }
            }
            while(s1 <= e1){
                tmpArr[k] = array[s1];
                k++;
                s1++;
            }
            while(s2 <= e2){
                tmpArr[k] = array[s2];
                k++;
                s2++;
            }
            //转换
            //递归右边结束,array[i] = arrTmp[i] 又会从0开始赋值,是错误的.
            //array[i+left] = tmpArr[i];
            // 可以避免错误,左边left =0相当于没有调整,右边left改变,进行调整正确赋值
            for (int i = 0; i < tmpArr.length; i++) {
                array[i+left] = tmpArr[i];
            }
        }
    
        //归并非递归写法
        //有了合并的函数,只需要研究怎样分解这个数组后调用合并函数合并即可
        public static void mergeSort2(int[] array){
            int gap = 1;
            while(gap < array.length){
                for (int i = 0; i < array.length; i+=gap*2) {
                    int left = i;
                    int mid = left + gap -1;
                    int right = mid + gap;
                    //mid和right在有些情况下会越界
                    if(mid >= array.length){
                        mid = array.length-1;
                    }
                    if(right >= array.length){
                        right = array.length-1;
                    }
                    merge(array,left,mid,right);
                }
    
                gap = gap*2;
    
    
            }
        }

## 8.计数排序 ##

public static void countSort(int[] array){
           //1.找到最大最小值
            int maxVal = array[0];
            int minVal = array[0];
            for (int i = 0; i < array.length; i++) {
                if(array[i] > maxVal){
                    maxVal = array[i];
                }
                if(array[i] < minVal){
                    minVal = array[i];
                }
            }
            //2.创建计数数组
            int len = maxVal-minVal +1 ;
            int[] countArr = new int[len];
            //3.遍历数组
            for (int i = 0; i < array.length; i++) {
                int val = array[i];
                countArr[val-minVal]++;
            }
            //4.覆盖
            int index = 0;
            for (int i = 0; i < countArr.length; i++) {
                while(countArr[i] > 0){
                    array[index] = i+minVal;
                    countArr[i]--;
                    index++;
                }
            }
        }