0
0

数据结构 Java数据结构 --- 十大排序

在这里插入图片描述

1.直接插入排序

1.1 动图演示

在这里插入图片描述

1.2 插入排序的思路:

  1. 从第一个元素开始,这里我们第一个元素是已排序的.
  2. 取下一个元素,和有序序列的元素从后往前比较.( 有序区间 : [0,i) )
  3. 如果得到的有序序列的元素 比 该元素大 则 将取得的有序元素往后放
  4. 重复3操作,直到得到的有序元素 比 该元素小, 或者 有序元素比完了.记录这个位置
  5. 然后将该元素放入到这个位置.
  6. 遍历数组,重复2~5的操作.

1.3 代码实现:

/**
     * 时间复杂度:
     *      最好的情况: O(n)
     *      最坏的情况: O(n^2)
     * 空间复杂度: O(1)
     * @param array
     */publicstaticvoidinsertSort(int[] array){for(int i =1; i < array.length; i++){int j = i -1;int tmp = array[i];while(j >=0){if(array[j]> tmp){
                    array[j +1]= array[j];
                    j--;}else{break;}}
            array[j +1]= tmp;}}

1.4 性能分析

时间复杂度(平均)时间复杂度(最坏)时间复杂度(最好)空间复杂度稳定性O(n^2)O(n^2)O(n)O(1)稳定
插入排序，初始数据越接近有序，时间效率越高。

2.希尔排序

2.1 原理

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数

gap

，把待排序文件中所有记录分成个

gap

组，所有距离为

gap

的记录分在同一组内，并对每一组内的记录进行排序。然后，取

gap = (gap/3)+1

，重复上述分组和排序的工作。当到达

gap=1

时，所有记录在统一组内排好序。

  1. 希尔排序是对直接插入排序的优化。
  2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。

在这里插入图片描述

2.2 动图演示

在这里插入图片描述

2.3 代码实现:

/**
     *
      * @param array 排序的数组
     * @param gap 每组的间隔 -> 数组
     */publicstaticvoidshell(int[] array,int gap){for(int i = gap; i < array.length ; i++){int tmp = array[i];int j = i - gap;while(j>=0){if(array[j]> tmp){
                     array[j + gap]= array[j];
                     j -= gap;}else{break;}}
             array[j + gap]= tmp;}}publicstaticvoidshellSort(int[] array){int gap = array.length;while(gap >1){
             gap =(gap /3)+1;// +1 保证最后一个序列是 1 (除几都行)shell(array,gap);}}

2.4 性能分析

时间复杂度(平均)时间复杂度(最坏)时间复杂度(最好)空间复杂度稳定性O(n^1.3)O(n^2)O(n)O(1)不稳定

3.直接选择排序

3.1 动图演示

在这里插入图片描述

3.2 代码实现:

/**
     * 时间复杂度:
     *      最好: O(n^2)
     *      最坏: O(n^2)
     * 空间复杂度: O(1)
     * 稳定性: 不稳定
     * @param array
     */publicstaticvoidselectSort(int[] array){for(int i =0; i < array.length -1; i++){for(int j = i +1; j <array.length ; j++){if(array[j]< array[i]){int tmp = array[i];
                    array[i]= array[j];
                    array[j]= tmp;}}}}

3.3 性能分析

时间复杂度(平均)时间复杂度(最坏)时间复杂度(最好)空间复杂度稳定性O(n^2)O(n^2)O(n^2)O(1)不稳定

4.堆排序

4.1 动图演示

在这里插入图片描述

4.2 代码实现:

publicstaticvoidsiftDown(int[] array,int root,int len){int parent = root;int child = root *2+1;while(child < len){if( child+1< len && array[child]< array[child+1]){
                child++;}//这里child下标就是左右孩子的最大值的下标if(array[child]> array[parent]){int tmp = array[child];
                array[child]= array[parent];
                array[parent]= tmp;
                parent = child;
                child = parent *2+1;}else{break;}}}publicstaticvoidcreateHeap(int[] array){for(int i =(array.length -1-1)/2; i >=0; i++){siftDown(array,i,array.length);}}publicstaticvoidheapSort(int[] array){createHeap(array);int end = array.length -1;while(end >0){int tmp = array[end];
            array[end]= array[0];
            array[0]=tmp;siftDown(array,0,end);
            end--;}}

4.3 性能分析

时间复杂度(平均)时间复杂度(最坏)时间复杂度(最好)空间复杂度稳定性O(n * log(n))O(n * log(n))O(n * log(n))O(1)不稳定

5.冒泡排序

5.1 动图演示

在这里插入图片描述

5.2 代码实现

publicstaticvoidBubbleSort(int[] array){for(int i =0; i < array.length -1; i++){boolean flg =false;for(int j =0; j < array.length -1- i ; j++){if(array[j+1]< array[j]){int tmp = array[j];
                    array[j]= array[j+1];
                    array[j+1]= tmp;
                    flg =true;}}if(!flg){break;}}}

5.3 性能分析

时间复杂度(平均)时间复杂度(最坏)时间复杂度(最好)空间复杂度稳定性O(n^2)O(n^2)O(n)O(1)稳定

6.快速排序

6.1 原理

  1. 从待排序区间选择一个数，作为基准值(pivot)；
  2. Partition: 遍历整个待排序区间，将比基准值小的（可以包含相等的）放到基准值的左边，将比基准值大的（可 以包含相等的）放到基准值的右边；
  3. 采用分治思想，对左右两个小区间按照同样的方式处理，直到小区间的长度 == 1，代表已经有序，或者小区间 的长度 == 0，代表没有数据。

6.2 动图演示

在这里插入图片描述

6.3 实现方法

6.3.1 Hoare法:

在这里插入图片描述

6.3.2 挖坑法:

在这里插入图片描述

6.4 代码实现

//Hoare法publicstaticvoidswap(int[] array,int i,int j){int tmp = array[i];
        array[i]= array[j];
        array[j]= tmp;}publicstaticintpartition1(int[] array,int low,int high){int i = low;int tmp = array[low];while(low < high){while(low < high && array[high]>= tmp){
                high--;}while(low < high && array[low]<= tmp){
                low++;}swap(array,low,high);}swap(array,i,low);return low;}//挖坑法publicstaticintpartition2(int[] array,int low,int high){int tmp = array[low];while(low < high){while(low < high && array[high]>= tmp){
                high--;}
            array[low]= array[high];while(low < high && array[low]<= tmp){
                low++;}
            array[high]= array[low];}
        array[low]= tmp;return low;}publicstaticvoidquick(int[] array,int start,int end){if(start >= end)return;int pivot =partition1(array,start,end);quick(array,start,pivot-1);quick(array,pivot+1,end);}publicstaticvoidquickSort(int[] array){quick(array,0,array.length-1);}

6.5 快排优化

6.5.1 三数取中法

publicstaticvoidswap(int[] array,int i,int j){int tmp = array[i];
        array[i]= array[j];
        array[j]= tmp;}publicstaticintpartition2(int[] array,int low,int high){int tmp = array[low];while(low < high){while(low < high && array[high]>= tmp){
                high--;}
            array[low]= array[high];while(low < high && array[low]<= tmp){
                low++;}
            array[high]= array[low];}
        array[low]= tmp;return low;}publicstaticvoidselectPivotMedianOFThree(int[] array,int start,int end,int mid){if(array[mid]> array[start]){swap(array,start,mid);}//此时mid下标的值肯定小于start下标的值 array[mid] <= array[start]if(array[mid]> array[end]){swap(array,mid,end);}//此时mid下标的值肯定小于end下标的值 array[mid] <= array[end]if(array[start]> array[end]){swap(array,start,end);}//此时有 array[mid] <= array[start] <= array[end]}publicstaticvoidquick1(int[] array,int start,int end){if(start >= end)return;int mid =(start + end)/2;selectPivotMedianOFThree(array,start,end,mid);int pivot =partition2(array,start,end);quick1(array,start,pivot-1);quick1(array,pivot+1,end);}publicstaticvoidquick1Sort(int[] array){quick1(array,0,array.length -1);}

6.5.2 加上直接插入排序

publicstaticvoidswap(int[] array,int i,int j){int tmp = array[i];
        array[i]= array[j];
        array[j]= tmp;}publicstaticvoidinsertSort2(int[] array,int start,int end){for(int i = start +1; i <= end; i++){int j = i +1;int tmp = array[i];while(j >=0){if(array[j]> tmp){
                    array[j+1]= array[j];}else{break;}}
            array[j+1]= tmp;}}publicstaticintpartition2(int[] array,int low,int high){int tmp = array[low];while(low < high){while(low < high && array[high]>= tmp){
                high--;}
            array[low]= array[high];while(low < high && array[low]<= tmp){
                low++;}
            array[high]= array[low];}
        array[low]= tmp;return low;}publicstaticvoidselectPivotMedianOFThree(int[] array,int start,int end,int mid){if(array[mid]> array[start]){swap(array,start,mid);}//此时mid下标的值肯定小于start下标的值 array[mid] <= array[start]if(array[mid]> array[end]){swap(array,mid,end);}//此时mid下标的值肯定小于end下标的值 array[mid] <= array[end]if(array[start]> array[end]){swap(array,start,end);}//此时有 array[mid] <= array[start] <= array[end]}publicstaticvoidquick2(int[] array,int start,int end){if(start >= end)return;if(end - start +1<=100){insertSort2(array,start,end);return;}int mid =(start + end)/2;selectPivotMedianOFThree(array,start,end,mid);int pivot =partition2(array,start,end);quick2(array,start,pivot-1);quick2(array,pivot+1,end);}publicstaticvoidquick2Sort(int[] array){quick2(array,0,array.length -1);}

6.6 非递归的实现

6.6.1 非递归思路

  1. 首先调用partition,找到pivot
  2. 然后把pivot的 左区间 和 右区间 的下标放到栈立马
  3. 判断栈是否为空,不为空,弹出栈顶的2个元素(注意:入栈的顺序 决定了出栈的顺序中的第一个元素是high的还是low的)
  4. 然后再进行调用partition,找pivot,
  5. 重复以上操作.

6.6.2 非递归代码实现

publicstaticvoidquickSort4(int[] array){
        Stack<Integer> stack =newStack<>();int low =0;int high = array.length -1;int pivot =partition2(array,low ,high);//左边有2个元素即以上if(pivot > low +1){
            stack.push(0);
            stack.push(pivot -1);}//右边有2个元素即以上if(pivot < high -1){
            stack.push(pivot +1);
            stack.push(high);}while(!stack.isEmpty()){
            high = stack.pop();
            low = stack.pop();
            pivot =partition2(array,low,high);//左边有2个元素即以上if(pivot > low +1){
                stack.push(0);
                stack.push(pivot -1);}//右边有2个元素即以上if(pivot < high -1){
                stack.push(pivot +1);
                stack.push(high);}}}

6.7 性能分析

时间复杂度(平均)时间复杂度(最坏)时间复杂度(最好)空间复杂度稳定性O(n * log(n))O(n^2)O(n * log(n))O(log(n))~O(n)不稳定

7.归并排序

7.1 原理

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子 序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
在这里插入图片描述
在这里插入图片描述

7.2 动图演示

在这里插入图片描述

7.3 代码实现—递归

publicstaticvoidmerge(int[] array,int low ,int high ,int mid){int s1 = low;int e1 = mid;int s2 = mid+1;int e2 = high;int[] tmp =newint[high - low +1];int k =0;while(s1 <= e1 && s2 <= e2){if(array[s1]<= array[s2]){
                tmp[k++]= array[s1++];}else{
                tmp[k++]= array[s2++];}}while(s1 <= e1){
            tmp[k++]= array[s1++];}while(s2 <= e2){
            tmp[k++]= array[s2++];}for(int i =0; i < tmp.length; i++){
            array[i+low]= tmp[i];}}publicstaticvoidmergeSortInternal(int[] array,int low ,int high){if(low >= high)return;int mid =(low + high)/2;mergeSortInternal(array,low,mid);mergeSortInternal(array,mid+1,high);merge(array,low,high,mid);}publicstaticvoidmergeSort(int[] array){mergeSortInternal(array,0,array.length -1);}

7.4 代码实现—非递归

publicstaticvoidmerge1(int[] array,int gap){int[] tmp =newint[array.length];int k =0;int s1 =0;int e1 = s1 + gap -1;int s2 = e1 +1;int e2 = s2 + gap -1> array.length ? array.length -1: s2 + gap -1;while(s2 < array.length){while(s1 <= e1 && s2 <= e2){if(array[s1]<= array[s2]){
                    tmp[k++]= array[s1++];}else{
                    tmp[k++]= array[s2++];}}while(s1 <= e1){
                tmp[k++]= array[s1++];}while(s2 <= e2){
                tmp[k++]= array[s2++];}

            s1 = e2 +1;
            e1 = s1 + gap -1;

            s2 = e1 +1;
            e2 = s2 + gap -1> array.length ? array.length -1: s2 + gap -1;}while(s1 <= array.length -1){
            tmp[k++]= array[s1++];}for(int i =0; i < tmp.length; i++){
            array[i]= tmp[i];}}publicstaticvoidmergeSort1(int[] array){for(int i =1; i < array.length; i*=2){merge1(array,i);}}

7.5 性能分析

时间复杂度(平均)时间复杂度(最坏)时间复杂度(最好)空间复杂度稳定性O(n * log(n))O(n * log(n))O(n * log(n))O(n)稳定

8.计数排序

当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 O(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。

8.1 算法的步骤：

（1）找出待排序的数组中最大和最小的元素
（2）统计数组中每个值为i的元素出现的次数，存入数组C的第i项
（3）对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
（4）反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

8.2 动图演示

在这里插入图片描述

8.3 代码实现:

publicstaticvoidCountingSort(int[] array){int maxValue =GetMaxValue(array);int bucketLen = maxValue +1;int[] bucket =newint[bucketLen];for(int value:array){
            bucket[value]++;}int index =0;for(int i =0; i < bucketLen; i++){while(bucket[i]>0){
                array[index++]= i;
                bucket[i]--;}}}publicstaticintGetMaxValue(int[] array){int maxValue = array[0];for(int i =0; i < array.length; i++){if(maxValue < array[i]){
                maxValue = array[i];}}return maxValue;}

8.4 性能分析

时间复杂度(平均)时间复杂度(最坏)时间复杂度(最好)空间复杂度稳定性O(n+k)O(n+k)O(n+k)O(k)稳定

9.桶排序

9.1 原理

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

为了使桶排序更加高效，我们需要做到这两点：

  1. 在额外空间充足的情况下，尽量增大桶的数量
  2. 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

9.2 算法的步骤:

  1. 设置一个定量的数组当作空桶；
  2. 遍历输入数据，并且把数据一个一个放到对应的桶里去；
  3. 对每个不是空的桶进行排序；
  4. 从不是空的桶里把排好序的数据拼接起来。

9.3 画图解析

在这里插入图片描述

9.4 代码实现

publicstaticvoidbucketSort(int[] arr){if(arr.length ==0){return;}int minValue = arr[0];int maxValue = arr[0];for(int value : arr){if(value < minValue){
                minValue = value;}elseif(value > maxValue){
                maxValue = value;}}//得到最大和最小元素int bucketNum =(maxValue - minValue)/ arr.length +1;//桶的数量
        ArrayList<ArrayList<Integer>> bucket =newArrayList<>(bucketNum);for(int i =0; i < bucketNum; i++){
            bucket.add(newArrayList<>());}//将元素放入到桶中for(int i =0; i < arr.length; i++){int num =(arr[i]- minValue)/ arr.length;
            bucket.get(num).add(arr[i]);}for(int i =0; i < bucket.size(); i++){//这里是比较,可以选择其他的方式实现,这里为了演示采取Collection的sort
            Collections.sort(bucket.get(i));}// 将桶中的元素赋值到原序列int index =0;for(int i =0; i < bucket.size(); i++){for(int j =0; j < bucket.get(i).size(); j++){
                arr[index++]= bucket.get(i).get(j);}}}

9.5 性能分析

时间复杂度(平均)时间复杂度(最坏)时间复杂度(最好)空间复杂度稳定性O(n+k)O(n^2)O(n+k)O(n+k)稳定

10.基数排序

10.1 算法的步骤:

  1. 取得数组中的最大数，并取得位数；
  2. arr为原始数组，从最低位开始取每个位组成radix数组；
  3. 对radix进行计数排序（利用计数排序适用于小范围数的特点）

10.2 动图演示

在这里插入图片描述

10.3 代码实现

publicstaticintgetNumLength(int num){if(num ==0)return1;int count =0;for(int i = num; i !=0; i /=10){
            count++;}return count;}publicstaticvoidRadixSort(int[] array){int maxValue = array[0];for(int i =0; i < array.length; i++){if(maxValue < array[i]){
                maxValue = array[i];}}int maxDigit =getNumLength(maxValue);int mod =10;int dev =1;for(int i =0; i < maxDigit; i++, dev *=10, mod *=10){int[][] counter =newint[mod *2][0];for(int j =0; j < array.length; j++){int bucket =((array[j]% mod)/ dev)+ mod;
                counter[bucket]=arrayAppend(counter[bucket], array[j]);}int pos =0;for(int[] bucket : counter){for(int value : bucket){
                    array[pos++]= value;}}}}publicstaticint[]arrayAppend(int[] arr,int value){
        arr = Arrays.copyOf(arr, arr.length +1);
        arr[arr.length -1]= value;return arr;}

10.4 性能分析

时间复杂度(平均)时间复杂度(最坏)时间复杂度(最好)空间复杂度稳定性O(nk)O(n2)O(n*k)O(n+k)稳定

总结

排序方法最好平均最坏空间复杂度稳定性冒泡排序O(n)数组有序O(n^2)O(n^2) 数组逆序O(1)稳定插入排序O(n)数组有序O(n^2)O(n^2) 数组逆序O(1)稳定选择排序O(n^2)O(n^2)O(n^2)O(1)不稳定希尔排序O(n)数组有序O(n^1.3)O(n^2)比较难构造O(1)不稳定堆排序O(n * log(n))O(n * log(n))O(n * log(n))O(1)不稳定快速排序O(n * log(n))O(n * log(n))O(n^2)最好O(log(n)) 最坏O(n)不稳定归并排序O(n * log(n))O(n * log(n))O(n * log(n))O(n)稳定计数排序O(n+k)O(n+k)O(n+k)O(k)稳定桶排序O(n+k)O(n+k)O(n^2)O(k)稳定计数排序O(n×k)O(n×k)O(n×k)O(k)稳定

标签： 数据结构 java 排序算法
本文转载自: https://blog.csdn.net/wwzzzzzzzzzzzzz/article/details/122409684
版权归原作者 wwzzzzzzzzzzzzz 所有， 如有侵权，请联系我们删除。
登录后发布评论

“数据结构 Java数据结构 --- 十大排序”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

机器人技术在安全领域的重要作用

安全学习记录——网络篇（一）

图腾柱PFC：HP1010为您的电动两轮车之旅提供绿色，高效，安全的动力

单元测试数据库回滚问题

这才是单元测试，之前我们都错了

【C语言基础】：字符函数和字符串函数

ChatGPT-Next-Web SSRF漏洞+XSS漏洞复现(CVE-2023-49785)

文章导航