【Java数据结构】排序

一、排序
- - 1.1 排序的概念
  - 1.2 排序的稳定性
  - 1.3 内部排序和外部排序
  - - 1.3.1 内部排序
    - 1.3.2 外部排序
二、插入排序
- - 2.1 直接插入排序
  - 2.2 希尔排序
三、选择排序
- - 3.1 选择排序
  - 3.2 堆排序
四、交换排序
- - 4.1 冒泡排序
  - 4.2 快速排序
  - - Hoare法：
    - 挖坑法：
    - 前后指针：
  - 4.3 快速排序的优化
  - - 4.3.1 三数取中法
    - 4.3.2 递归到小的子区间时，使用直接插入排序
  - 4.4 非递归快速排序
五、归并排序
- - 5.1 递归归并排序
  - 5.2 非递归归并排序
六、总结

博客最后附有整篇博客的全部代码！！！

一、排序

1.1 排序的概念

排序是计算机科学中一个非常基础且重要的概念，它指的是将一组对象按照某种顺序排列的过程。排序算法是实现排序功能的具体方法，通过对数据进行比较、交换或移动等操作，使数据元素按照指定的顺序排列。

1.2 排序的稳定性

稳定性是一个重要的概念，它描述了排序算法是否能够保持相同元素的相对顺序不变。

排序稳定性：
一个排序算法是稳定的，如果在排序过程中，两个具有相同键值（或值）的元素在排序前后的相对顺序保持不变。换句话说，如果元素A和B在排序前满足A在B之前，并且它们的键值相同，那么排序后A仍然在B之前。

例如：
下面一组数据，里面有两个相同的值‘8’（为了展现它们的相对位置，我们将两个相同值的‘8’用不同元素表示出来）。在排序之前‘8’
在这里插入图片描述

1.3 内部排序和外部排序

1.3.1 内部排序

内部排序是指在排序过程中，所有待排序的数据都能同时存储在内存中进行处理。由于内存访问速度较快，内部排序通常效率较高，但受限于内存容量，适用于数据量较小的场景。

特点：
存储：所有数据存储在内存中。
效率：通常较快，因为内存访问速度快。
适用场景：数据量较小（通常在几万甚至几十万以内）。

1.3.2 外部排序

外部排序是指待排序的数据量过大，无法全部加载到内存中，需要借助外存（如磁盘）来完成排序的过程。外部排序通常涉及将数据分块处理，排序后再合并。

特点：
存储：数据主要存储在外存（如磁盘），内存仅用于存储部分数据。
效率：通常较慢，因为外存访问速度远低于内存。
适用场景：数据量巨大（如数百万甚至数十亿条记录），无法全部加载到内存中。

二、插入排序

2.1 直接插入排序

思想：

将待排序的元素逐个插入到已经排好序的序列中，从而逐步扩展有序序列的长度，直到所有元素都被插入，整个序列变为有序。

时间复杂度：O(N^2)。
空间复杂度：O(1)。
稳定性：稳定。

代码:

    public void insertSort(int[] array){
        int tmp=0;
        for(int i=1;i<array.length-1;i++){
            tmp=array[i];
            int j=i-1;
            for(;j>=0;j--){
                if(tmp<array[j]){
                    array[j+1]=array[j];
                }else{
                    break;
                }
            }
            array[j+1]=tmp;
        }
    }

2.2 希尔排序

思想：

希尔排序（Shell Sort）是插入排序的一种改进版本，通过将数组分成多个子序列进行排序，逐步缩小子序列的间隔（增量），最终使整个数组有序。
其核心思想如下：
选择增量序列：初始增量通常为数组长度的一半，随后逐步减小，直到增量为1。
分组排序：按照当前增量将数组分成多个子序列，对每个子序列进行插入排序。
逐步缩小增量：重复上述过程，直到整个数组基本有序，最后使用增量为1的插入排序完成最终排序。

时间复杂度：O(n^1.3 )至 O( n^1.5)之间。
空间复杂度：O(1)。
稳定性：不稳定。

代码：

   public void shellSort(int[] array){
        int gap=array.length;
        while(gap>1){
            gap=gap/2;
            shell(array,gap);
        }
    }

    private void shell(int[] array, int gap) {
        int tmp=0;
        for (int i = gap; i < array.length ; i++) {
            tmp=array[i];
            int j=i-gap;
            for(;j>=0;j-=gap){
                if(tmp<array[j]){
                    array[j+gap]=array[j];
                }else{
                    break;
                }
            }
            array[j+gap]=tmp;
        }
    }

三、选择排序

3.1 选择排序

思想：

选择排序是一种简单直观的排序算法。它的核心思想是：

每次从未排序的部分中选择最小（或最大）的元素，并将其放到已排序部分的末尾。
重复上述过程，直到所有元素都被排序。

时间复杂度：O(N^2)。
空间复杂度：O(1)。
稳定性：不稳定。

代码：

 public 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[minIndex]>array[j]){
                    minIndex=j;
                }
            }
            int tmp=array[i];
            array[i]=array[minIndex];
            array[minIndex]=tmp;
        }
    }

延伸：
思路：

定义两个变量‘minIndex’和‘maxIndex’来接收遍历完一遍数组得到的最大值和最小值下标，将得到的最大值和最小值下标分别与这组数组的最左边和最右边的值交换，以此类推。

时间复杂度：O(n²)
空间复杂度：O(1)
稳定性：不稳定

代码：

    public void selectSort2(int[] array) {
        int left=0;
        int right=array.length-1;
        int len=array.length;
        while(left<right){
            int minIndex=left;
            int maxIndex=left;
            for (int i = left; i < len; i++) {
                if(array[i]<array[minIndex]){
                    minIndex=i;
                }
                if(array[i]>array[maxIndex]){
                    maxIndex=i;
                }
            }
            swap(array,left,minIndex);
            left++;
            swap(array,right,maxIndex);
            right--;
            len--;
        }

    }
    public void swap(int[] array,int x,int y){
        int tmp=array[x];
        array[x]=array[y];
        array[y]=tmp;
    }

3.2 堆排序

思路：

建立大根堆，将大根堆的堆顶元素和最后一个元素进行交换，交换完后将剩下的堆重新调整，以此类推。

时间复杂度：O(N*logN)。
空间复杂度：O(1)。
稳定性：不稳定。

代码：

public void heapSort(int[] array){
        //创建堆
        createHeap(array);
        int end=array.length-1;
        while(end>0){
            swap(array,0,end);
            shiftDown(array,0,end);
            end--;
        }
    }
    public void createHeap(int[] array){
        for(int parent=(array.length-1-1)/2;parent>=0;parent--){
            shiftDown(array,parent,array.length);
        }
    }
    public void shiftDown(int[] array,int parent,int length){
        int child =parent*2+1;
        while(child<length){
            //如果孩子存在，找到左右孩子中较小的孩子，用child标记
            if (child + 1 < length && array[child] < array[child+1]) {
                child++;
            }
            if(array[parent]<=array[child]){
                swap(array,parent,child);
                parent=child;
                child=parent*2+1;
            }else{
                break;
            }
        }
    }

四、交换排序

4.1 冒泡排序

思想：

核心思想是通过相邻元素之间的比较和交换，逐步将最大（或最小）的元素“冒泡”到数组的末尾（或开头）。这个过程重复进行，直到整个数组有序。

时间复杂度：O(N^2) 。
空间复杂度：O(1)。
稳定性：稳定。

代码：

public void bubbleSort(int[] array){
        boolean flag=true;
        for (int i = 0; i < array.length-1; i++) {
            for (int j = 0;j<array.length-1-i;j++ ){
                if(array[j]>array[j+1]){
                    swap(array,j,j+1);
                    flag=false;
                }
            }
            if(flag){
                break;
            }
        }
    }

4.2 快速排序

思想：

核心思想是通过分区操作将数组分为两部分，使得一部分的所有元素都小于（或等于）另一部分的所有元素，然后递归地对这两部分进行排序。

时间复杂度：O(N*logN)至O(n^2)。
空间复杂度：O(logN)至O(N)。
稳定性：不稳定。

Hoare法：

思路：

选定序列第一个为基准，从后边往前找到比基准小的停下来，从前边找到比基准大的停下来，交换直到左右相遇，相遇下标的值与基准交换。

代码:

 public void quickSort(int[] array){
        hoareSort(array,0,array.length-1);
    }

    public void hoareSort(int[] array,int start,int end) {
        if(start>=end){
            return;
        }
        int pivot = partition(array, start, end);
        hoareSort(array,start,pivot-1);
        hoareSort(array,pivot+1,end);
    }

    private int partition(int[] array, int left, int right) {
        int flag=left;
        while(left<right){
          while(left<right&&array[right]>=array[flag]){
                right--;
            }
            while(left<right&&array[left]=<array[flag]){
                left++;
            }
            swap(array,left,right);
        }
        swap(array,left,flag);
        return left;
    }

挖坑法：

思路：

选定序列第一个为基准，从后往前找，找到小于基准的，将其放到基准的位置，接下来从前往后找，找到比基准大的，放到先前后面找到的比基准小的位置，以此类推。

代码：

    private int partition2(int[] array, int left, int right) {
        int flag=array[left];
        while(left<right){
            while(left<right&&array[right]>=flag){
                right--;
            }
            array[left]=array[right];
            while(left<right&&array[left]<=flag){
                left++;
            }
            array[right]=array[left];
        }
        array[left]=flag;
        return left;
    }

前后指针：

思路：

选定序列第一个为基准，定义两个prev和cur来标记下标，遍历序列，满足cur下标的值小于基准，并且prev++下标和cur下标不在同一个下标，交换prev和cur下标的值，如果不满足条件，cur++。

代码：

    private int partition3(int[] array, int left, int right) {
        int prev=left;
        int cur=prev+1;
        while(cur<=right){
           if(array[cur]<array[left]&&array[++prev]!=array[cur]){
               swap(array,prev,cur);
           }
           cur++;
        }
        swap(array,prev,left);
        return prev;
    }

4.3 快速排序的优化

4.3.1 三数取中法

优点：

优化性能：通过选择中值作为基准值，减少了因数据分布不均匀而导致的性能退化。
提高稳定性：在处理接近有序或完全逆序的数据时，性能更加稳定。

代码：

 public void hoareSort(int[] array,int start,int end) {
        if(start>=end){
            return;
        }
        int midIndex=getNumber(array,start,end);
        swap(array,start,midIndex);

        int pivot = partition(array, start, end);
        hoareSort(array,start,pivot-1);
        hoareSort(array,pivot+1,end);
    }
    private int getNumber(int[] array,int left,int right){
        int mid=(left+right)/2;
        if(array[left]<array[right]){
            if(array[mid]<array[left]){
                return left;
            } else if (array[mid]>array[right]) {
                return right;
            }else{
                return mid;
            }
        }else{
            if(array[mid]<array[right]){
                return right;
            } else if (array[mid]>array[left]) {
                return left;
            }else{
                return mid;
            }
        }
    }

4.3.2 递归到小的子区间时，使用直接插入排序

优点：

因为直接插入排序的特点就是越有序越快。

代码：

    public void hoareSort(int[] array,int start,int end) {
        if(start>=end){
            return;
        }
//        int midIndex=getNumber(array,start,end);
//        swap(array,start,midIndex);

        if (end - start+1 <= 10) {
            insertSortRange(array,start,end);
            return;
        }
        int pivot = partition(array, start, end);
        hoareSort(array,start,pivot-1);
        hoareSort(array,pivot+1,end);
    }

    private void insertSortRange(int[] array, int start, int end) {
        int tmp=0;
        for(int i=start+1;i<=end;i++){
            tmp=array[i];
            int j=i-1;
            for(;j>=start;j--){
                if(tmp<array[j]){
                    array[j+1]=array[j];
                }else{
                    break;
                }
            }
            array[j+1]=tmp;
        }
    }

4.4 非递归快速排序

思想：

通过挖坑法先求得基准下标
通过基准下标将基准左右两边序列的start和end存进栈中，存入栈中的先后顺序要一致
通过pop（）弹出start和end，再通过挖坑法求得基准下标，以此类推，当栈为空，则证明已经排序好了

代码：

    public void quickNor(int[] array,int start,int end) {
        Stack<Integer> stack=new Stack<>();
        int pivot = partition2(array, start, end);
        if(pivot>start+1){
            stack.push(start);
            stack.push(pivot-1);
        }
        if(pivot<end-1){
            stack.push(pivot+1);
            stack.push(end);
        }
        while(!stack.isEmpty()){
            end=stack.pop();
            start=stack.pop();
            pivot=partition2(array, start, end);
            if(pivot>start+1){
                stack.push(start);
                stack.push(pivot-1);
            }
            if(pivot<end-1){
                stack.push(pivot+1);
                stack.push(end);
            }
        }
    }

五、归并排序

5.1 递归归并排序

思路：

归并排序是一种分治排序算法，其核心思想是将数组分成多个小部分，分别对这些小部分进行排序，然后逐步合并这些有序部分，最终得到一个完全有序的数组。

时间复杂度：O(N*logN)。
空间复杂度：O(N)。
稳定性：稳定。

代码:

    public void mergeSort(int[] nums) {
        mergeSortSplit(nums, 0, nums.length - 1);
    }

    private void mergeSortSplit(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        //分解
        int mid = (left + right) / 2;
        mergeSortSplit(nums, left, mid-1);
        mergeSortSplit(nums, mid + 1, right);
        //合并
        merge(nums, left, mid, right);
    }

    private void merge(int[] nums, int left, int mid, int right) {
        int[] tmp = new int[right - left + 1];
        int k=0;
        int s1=left;
        int s2=mid + 1;
        while(s1<=mid&&s2<=right){
            if(nums[s1]<=nums[s2]){
                tmp[k++]=nums[s1++];
            }else{
                tmp[k++]=nums[s2++];
            }
        }
        while(s1<=mid){
            tmp[k++]=nums[s1++];
        }
        while(s2<=right){
            tmp[k++]=nums[s2++];
        }
        for(int i=left; i<k; i++){
            nums[i]=tmp[i];
        }
    }

5.2 非递归归并排序

    public void mergeSortNor(int[] array){
        int gap=1;
        while(gap<array.length){
            for(int i=0;i<array.length;i=i+gap*2){
                int left=i;
                int mid=left+gap-1;
                if(mid>=array.length){
                    mid=array.length-1;
                }
                int right=mid+gap;
                if(right>=array.length){
                    right=array.length-1;
                }
                merge(array,left,mid,right);
            }
            gap*=2;
        }
    }