排序算法

Scroll Down

912. 给你一个整数数组 nums,请你将该数组升序排列。

示例 1:
输入:nums = [5,2,3,1]
输出:[1,2,3,5]

示例 2:
输入:nums = [5,1,1,2,0,0]
输出:[0,0,1,1,2,5]

提示:
1 <= nums.length <= 50000
-50000 <= nums[i] <= 50000


简介

排序算法是用来根据元素对应的比较运算符重新排列给定的数组的算法,输出的数组是一个根据比较符从小到大或者从大到小依次排列的数组。比较运算符是用于确定相应数据结构中元素的新顺序,比如在整数数组里面,对应的比较符号就是大于或者小于号,用户也可以自己定义对应的比较运算符。
主流的排序算法主要有以下几种,参照极客时间《数据结构与算法之美》的图片
fb8394a588b12ff6695cfd664afb17cd
针对三种不同的复杂度的排序算法,以力扣912题展开分析。

冒泡排序

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较,看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置,会重复N次

// 冒泡排序,a表示数组,n表示数组大小
public void bubbleSort(int[] a, int n) {
  if (n <= 1) return;
 for (int i = 0; i < n; ++i) {
    // 提前退出冒泡循环的标志位
    boolean flag = false;
    for (int j = 0; j < n - i - 1; ++j) {
      if (a[j] > a[j+1]) { // 交换
        int tmp = a[j];
        a[j] = a[j+1];
        a[j+1] = tmp;
        flag = true;  // 表示有数据交换      
      }
    }
    if (!flag) break;  // 没有数据交换,提前退出
  }
}

插入排序

插入排序和冒泡一样也是有两种操作,一种是元素的比较,一种是元素的移动。当我们需要将一个数据 a 插入到已排序区间时,需要拿 a 与已排序区间的元素依次比较大小,找到合适的插入位置。找到插入点之后,我们还需要将插入点之后的元素顺序往后移动一位,这样才能腾出位置给元素 a 插入。

public void insertSort(int[] a, int n) {
  if (n <= 1) return;

  for (int i = 1; i < n; ++i) {
    int value = a[i];
    int j = i - 1;
    // 查找插入的位置
    for (; j >= 0; --j) {
      if (a[j] > value) {
        a[j+1] = a[j];  // 数据移动
      } else {
        break;
      }
    }
    a[j+1] = value; // 插入数据
  }
}
 /**
   *
   * @param arrays
   * @param <T>
   */
public static <T extends Comparable<? super T>> void insertSort(T[] arrays) {
        int j;
       for (int i=1;i<arrays.length;i++){
           T t=arrays[i];
           for( j=i;j>0&&t.compareTo(arrays[j-1])<0;j--){
               arrays[j]=arrays[j-1];
           }
           arrays[j]=t;
       }
    }

希尔排序

相较于插入排序而言,希尔排序可谓是插入排序的一次改进,应为插入排序会在j~0的间隔逐个比较,而希尔则是在将逐个比较的间隔增加,这样来缩减增量。

 public static <T extends Comparable<? super T>> void shellSort(T[] arrays) {
        int i;
        for(int gap= arrays.length/2;gap>0;gap/=2){
            for (int j=gap;j<arrays.length;j++){
                T t=arrays[j];
                for(i=j;i>=gap&&t.compareTo(arrays[i-gap])<0;i-=gap){
                    arrays[i]=arrays[i-gap];
                }
                arrays[i]=t;
            }
        }
    }

选择排序

先找到前n个元素中最大的值,然后和最后一个元素交换,这样保证最后一个元素一定是最大的,然后找到前n-1个元素中的最大值,和第n-1个元素进行交换,然后找到前n-2个元素中最大值,和第n-2个元素交换,依次类推到第2个元素,这样就得到了最后的排序数组。

private void selectSort(int[] nums) {
    for (int i = nums.length - 1; i > 0; i--) {
        int maxIndex = 0;         // 最大元素的位置
        for (int j = 0; j <= i; j++) {
            if (nums[maxIndex]<nums[j]) {
                maxIndex = j;
            }
        }
        swap(nums, maxIndex, i);   // 把这个最大的元素移到最后
    }
}

冒泡排序,插入排序和选择排序来分析$O({n^2})$的,如果对小规模数据进行排序,可以选择时间复杂度是 O(n2) 的算法;如果对大规模数据进行排序,时间复杂度是 $O(Nlog_n)$ 的算法更加高效

归并排序

核心是要对排序一个数组,我们先把数组从中间分成前后两部分,然后对前后两部分分别排序,再将排好序的两部分合并在一起,这也就是分治思想。分治,分而治之,将一个大问题分解成小的子问题来解决。小的子问题解决了,大问题也就解决了。这样整个数组就都有序了代码如下所示。

 public  void mergeSort(int[] arrays,int start,int end) {
        if (start>=end){
            return;
        }
        int mid=(end+start)/2;
        mergeSort(arrays,start,mid);
        mergeSort(arrays,mid+1,end);
        mergeArray(arrays,start,mid,end);
    }

    private void mergeArray(int[] arrays, int start, int mid, int end) {
        int aStart=start,aEnd=mid;
        int bStart=mid+1,bEnd=end;
	//定义额外的存储 空间换时间
        int[] result=new int[end-start+1];
        int k=0;
        while(aStart<=aEnd&&bStart<=bEnd){
            if (arrays[aStart]<=arrays[bStart]){
                result[k++]=arrays[aStart++];
            }else {
                result[k++]=arrays[bStart++];
            }
        }
        for (;bStart<=bEnd;bStart++){
            result[k++]=arrays[bStart];
        }
        for (;aStart<=aEnd;aStart++){
            result[k++]=arrays[aStart];
        }
        for(int a=0;a<result.length;a++){
            arrays[start+a]=result[a];
        }
    }
public static <T extends Comparable<? super T>> T[] mergeSort(T[] arrays,int left,int right){
        if (left<right){
            int mid=(left+right)/2;
            mergeSort(arrays,left,mid);
            mergeSort(arrays,mid+1,right);
            merge(arrays,left,mid,mid+1,right);
        }
        return arrays;

    }

    private static <T extends Comparable<? super T>> void merge(T[] arrays, int left, int mid, int rightA, int right) {
        int leftStart=left;
        int leftEnd=mid;
        int rightStart=rightA;
        int rightEnd=right;
        int result=0;
        Comparable[] temp = new Comparable[right-left+1];
        while(leftStart<=leftEnd&&rightStart<=rightEnd){
            if(arrays[leftStart].compareTo(arrays[rightStart])<=0){
                temp[result++]=arrays[leftStart++];
            }else {
                temp[result++]=arrays[rightStart++];
            }
        }
        while (leftStart<=leftEnd){
            temp[result++]=arrays[leftStart++];
        }
        while (rightStart<=rightEnd){
            temp[result++]=arrays[rightStart++];
        }
        for(int i=0;i<temp.length;i++){
            arrays[left+i]=(T)temp[i];
        }

    }

快速排序算法

也就是我们面试总遇到的面试官说会写快排吗。来写一个的那个快排,还是分治思想。乍看起来,它有点像归并排序,但是完全不一样,快排的核心在于选定一块分区某个值的索引,让分区中比这个基准值大的都放在其左或者右,小于基准值的和大于的存放相反。前面 startstandardIndex -1 之间都是小于 standardValue的,中间是 standardValue,后面的 standardIndex +1end 之间是大于 standardValue的,递归完毕,直到区间缩小为 1,就说明所有的数据都有序了。

  public void quickSort(int[] arrays,int start,int end) {
        if (start>end) return;
        int standard=partation(arrays,start,end);
        quickSort(arrays,start,standard-1);
        quickSort(arrays,standard+1,end);
    }
    public int partation(int[] arrays,int start,int end){
	//随机处理基准值,避免递归过深
        int standardIndex =new Random().nextInt(end-start+1)+start;
        int standardValue=arrays[standardIndex];
        swap(arrays,standardIndex,end);
        int r=start;
        for(int i=start;i<=end-1;i++){
            if (arrays[i]<standardValue){
                if(i>r) {
                    swap(arrays, i, r);
                }
                r++;
            }
        }
        swap(arrays,r,end);
        return r;

    }
    public void swap(int[] arrays,int start,int end){
        int temp=arrays[end];
        arrays[end]=arrays[start];
        arrays[start]=temp;
    }
优化分区基准选取

如果数据原来就是有序的或者接近有序的,每次分区点都选择最后一个数据,那快速排序算法就会变得非常糟糕,时间复杂度就会退化为$O({n^2})$的。
实际上出现的主要原因还是因为我们分区点选得不够合理。所以需要优化基准的选取,例如代码中的随机数选取。

快速选择算法

学会了快排的思想,你可以轻松拿下*如何在$O()$ 的时间复杂度内查找一个无序数组中的第 K 大元素
题目分析:我们选择数组区间 A[0…n-1]的最后一个元素 A[n-1]作为 pivot,对数组 A[0…n-1]原地分区,这样数组就分成了三部分,A[0…p-1]、A[p]、A[p+1…n-1]。如果 p+1=K,那 A[p]就是要求解的元素;如果 K>p+1, 说明第 K 大元素出现在 A[p+1…n-1]区间,我们再按照上面的思路递归地在 A[p+1…n-1]这个区间内查找。同理,K<p+1,那我们就在 A[0…p-1]区间查找。直接上代码。

//partation和上文一样,从小到大排序,返回第K个大的元素
 public int quickFindK(int[] arrays,int k) {
        int start=0,end=arrays.length-1;
        k=arrays.length-k;
        while(start<=end){
            int standard=partation(arrays,start,end);
            if (standard>k){
                start=standard+1;
            }else if (standard<k){
                end=standard-1;
            }else {
                return arrays[standard];
            }
        }
        return -1;
    }

当然这个问题你也可以使用小顶堆来处理,Java中的优先队列默认是小顶堆,维护K个容量的小顶堆的堆顶元素就是数组中第K个大的元素。不多bb直接上代码

    public int findKMax(int[] nums,int k){
        PriorityQueue<Integer> priorityQueue=new PriorityQueue();
        for(int i=0;i<nums.length;i++){
            priorityQueue.offer(nums[i]);
            if (priorityQueue.size()>k){
                priorityQueue.poll();
            }
        }
        return priorityQueue.peek();
    }