Java数据结构与算法

Java数据结构与算法：排序算法

2020-07-10  本文已影响0人  Patarw

一、基本介绍

在介绍排序算法之前，我们首先需要了解算法的时间复杂度来衡量各个算法的效率：

时间复杂度的基本概念

常见的几个时间复杂度

1.常数阶O(1)

无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是O(1)：


上述代码在执行的时候，它消耗的时候并不随着某个变量的增长而增长，那么无论这类代码有多长，即使有几万几十万行，都可以用O(1)来表示它的时间复杂度。

2.对数阶O(log2n)

设2的t次方等于n，看需要乘多少个2，i才能等于n，故时间复杂度为O(log2n)

3.线性阶O(n)

这段代码，for循环里面的代码会执行n遍，因此它消耗的时间是随着n的变化而变化的，因此这类代码都可以用O(n)来表示它的时间复杂度

4.线性对数阶O(nlogN)

线性对数阶O(nlogN) 其实非常容易理解，将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是 n * O(logN)，也就是O(nlogN)

5.平方阶O(n²)

平方阶O(n²) 就更容易理解了，如果把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²)，这段代码其实就是嵌套了2层n循环，它的时间复杂度就是 O(n * n)，即 O(n²) 如果将其中一层循环的n改成m，那它的时间复杂度就变成了 O(m * n)

平均时间复杂度与最坏时间复杂度

算法的空间复杂度

二、多种排序方法

2.1冒泡排序和选择排序

这两个相信大家大学应该都学过，这里就不过多赘述了。

2.2插入排序

代码：
 public static void main(String[] args) {   
 int[] arr = {5,6,3,9,1,4};

 for(int i = 1;i<arr.length;i++) {
     int value = arr[i];
     int index = i-1;
     while(index>=0 && value < arr[index]) {
         arr[index+1] = arr[index];
         index--;
     }
     arr[index+1] = value;
  }
 
 for(int i = 0;i<arr.length;i++) {
     System.out.println(arr[i]);
 }

}

2.3希尔排序

public static void main(String[] args) {    
 int[] arr = {8,9,1,7,2,3,5,4,6,0};
 int temp = 0;
 for(int gap = arr.length/2;gap>0;gap = gap/2) {
     for(int i = gap;i<arr.length;i++) {
         for(int j = i-gap;j>=0;j -= gap) {
             if(arr[j]>arr[j+gap]) {
                 temp = arr[j];
                 arr[j] = arr[j+gap];
                 arr[j+gap] = temp;
             }          
         }
     }
     System.out.println(Arrays.toString(arr));
 }
}

  public static void main(String[] args) {  
 int[] arr = {8,9,1,7,2,3,5,4,6,0};
 //下面的代码和插入法相似
 for(int gap = arr.length/2;gap>0;gap = gap/2) {
     for(int i = gap;i<arr.length;i++) {
      int index = i - gap;
      int temp = arr[i];
      while(index>=0 && temp < arr[index]) {
             arr[index+gap] = arr[index];
             index -= gap;
         }
      arr[index+gap] = temp;
     }
     System.out.println(Arrays.toString(arr));
 }
}

2.4快速排序法

(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。

(2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。 [2]

(3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。 [2]

(4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

2.5归并排序法

 public static void mergeSort(int[] arr, int left, int right,int[] temp) {
     if(left < right) {
       int mid = (left + right)/2;
       mergeSort(arr,left,mid,temp);
       mergeSort(arr,mid+1,right,temp);
       merge(arr,left,mid,right,temp);
     }
    }
 
 public static void merge(int arr[],int left,int mid,int right,int[] temp) {
     int l = left;
     int m = mid + 1;
     int t = 0;
     while(l <= mid && m <= right) {
         if(arr[l] <= arr[m]) {
         temp[t] = arr[l];
         l++;
         t++;
     }else {
         temp[t] = arr[m];
         m++;
         t++;
     }
     }
    
     while(l <= mid) {
         temp[t] = arr[l];
         l++;
         t++;
     }
     while(m <= right) {
         temp[t] = arr[m];
         m++;
         t++;
     }
     t = 0;
     int tempLeft = left;
     while(tempLeft <= right) {
         arr[tempLeft] = temp[t];
         tempLeft++;
         t++;
     }
 }
    public static void main(String[] args) {
        int[] arr = new int[] { 9, 8, 7, 6, 5, 4, 3, 2, 10 };
        int[] temp = new int[arr.length];
         mergeSort(arr, 0, arr.length - 1,temp);
       System.out.println(Arrays.toString(arr));
    }

2.6基数排序法

三、各排序方法的比较

上一篇 下一篇

猜你喜欢

热点阅读