Java算法基础——排序

快来打我* 2022-05-19 02:16 196阅读 0赞

*   *  1. 约定
     *  2. 插入排序
        
         *  2.1 算法思想
         *  2.2 时间复杂度
         *  2.3 程序清单
     *  3. 冒泡排序
        
         *  3.1 算法思想
         *  3.2 时间复杂度
         *  3.3 程序清单
     *  4. 归并排序
        
         *  4.1 算法思想
         *  4.2 时间复杂度
         *  4.3 代码清单
     *  5. 快速排序
        
         *  5.1 算法思想
         *  5.2 时间复杂度
         *  5.3 代码清单
     *  6. 堆排序
        
         *  6.1 算法思想
         *  6.2 堆存储
         *  6.3 添加新的节点
         *  6.4 删除根节点
         *  6.5 时间复杂度
     *  7. 总结
        
         *  7.1 关键术语
         *  7.2 小结

## 1. 约定 ##

为了简单起见，在这里约定：

*  要排序的数据是整数
 *  数据存储在数组中
 *  数据以升序排列

## 2. 插入排序 ##

### 2.1 算法思想 ###

重复的将新的元素插入到一个排好序的子线性表中，直到整个线性表排好序

### 2.2 时间复杂度 ###

*O*(*n*2)  O ( n 2 )

### 2.3 程序清单 ###

package sort;
    /* * 插入排序练习，时间复杂度O(n^2) */
    public class InsertionSort {
    
      public static int[] insertionSort(int[] list) {
        int currentValue,num;
        for(int order = 1; order < list.length; order++) {
          //currentValue记录当前需要排序的值,初始值从第二个开始
          currentValue = list[order];
          //如果等待插入元素小于最后一个元素，那么就将大元素外移，以此类推
          for(num = order - 1; 
              num >= 0 && list[num] > currentValue; num--) {
            list[num + 1] = list[num];
          }
          //此处加一的目的是因为最后一次循环多减了1
          list[num + 1] = currentValue;
        }
        return list;
      }
    
      public static void main(String[] args) {
        int[] list = {
       3,5,2,8,4,7,5};
        list = insertionSort(list);
        for(int n : list) {
          System.out.println(n);
        }
      }
    }

## 3. 冒泡排序 ##

### 3.1 算法思想 ###

在每次遍历中连续比较相邻的元素，如果元素没有按照顺序排列就互换值。由于最小的值像“气泡”一样逐渐浮向顶部，较大值沉向底部，所以称为冒泡排序。第一次遍历后，最后一个元素成为数组中的最大数。

### 3.2 时间复杂度 ###

*O*(*n*)=*n*2  O ( n ) = n 2

### 3.3 程序清单 ###

package sort;
    /* * 冒泡排序练习，方向递增，时间复杂度O(n^2) */
    public class BubbleSort {
      public static int[] bubbleSort(int[] list) {
        boolean needNext = true;
        //n次冒泡排序，每次将一个最大值放到尾部，同时减少无用的排序
        for(int times = 1; times <= list.length && needNext == true; times++) {
          needNext = false;
          //每次两两比较，将大的后移
          for(int i = 0; i < list.length - times; i++) {
            //如果在
            if(list[i] > list[i+1]) {
              int temp = list[i+1];
              list[i+1] = list[i];
              list[i] = temp;
              needNext = true;
            }
          }
        }
        return list;
      }
    
      public static void main(String[] args) {
        int[] list1 = {
       23,3,5,34,2,6,7,5,12,11};
        list1 = bubbleSort(list1);
        for(int n : list1) {
          System.out.print(n + " ");
        }
      }
    }

## 4. 归并排序 ##

### 4.1 算法思想 ###

将数组分为两半，对每部分递归地应用归并排序。在两部分排好序后，对他们进行归并。

### 4.2 时间复杂度 ###

*O*(*n*)=*n*log*n*  O ( n ) = n log ⁡ n

### 4.3 代码清单 ###

package sort;
    /* * 18.7.6 * 归并排序练习，从小到大 * * 算法思想：将待排序的数组递归二分，直到只剩一个元素， * 然后边排序边合并，最终得到排好序的数组 * * 时间复杂度：二分与组合的次数相同，每次需要的次数k=log2 n,即为2logn * 每次合并比较的次数最多为n-1，移动最多为n，总计2n-1 * 综上所述时间复杂度O(n)=nlongn */
    public class MergeSort {
      //将传递的数组一直递归二分，形成一个二叉树，然后二分完之后再递归合并
      public static void mergeSort(int[] list) {
        if(list.length > 1) {
          //将前半部分循环递归二分
          int[] leftHalf = new int[list.length / 2];
          System.arraycopy(list, 0, leftHalf, 0, list.length / 2);
          mergeSort(leftHalf);
    
          //将后半部分循环递归二分
          int rightHalfLength = list.length - list.length / 2;
          int[] rightHalf = new int[rightHalfLength];
          System.arraycopy(list, list.length / 2, rightHalf, 0, rightHalfLength);
          mergeSort(rightHalf);
    
          //每个二叉树的节点都包含这个函数，然后回溯的时候调用
          merge(leftHalf, rightHalf, list);
        }
      }
    
      //合并并排序好新的数组
      public static void merge(int[] left, int[] right, int[] temp) {
        int leftIndex = 0;
        int rightIndex = 0;
        int tempIndex = 0;
    
        //回溯递归合并排序，最先进入的是单元素集合
        while(leftIndex < left.length && rightIndex < right.length) {
          if(left[leftIndex] < right[rightIndex]) {
            //自加符号在后面是先返回当前值然后自增
            temp[tempIndex++] = left[leftIndex++];
          }
          else {
            temp[tempIndex++] = right[rightIndex++];
          }
        }
    
        //后面的两个while循环是为了将剩余的量加入进去
        //按照之前的回溯递归，他们肯定是已经按从小到大排好序的
        while(leftIndex < left.length) {
          temp[tempIndex++] = left[leftIndex++];
        }   
        while(rightIndex < right.length) {
          temp[tempIndex++] = right[rightIndex++];
        }
      }
    
      public static void main(String[] args) {
        int[] list1 = {
       2,324,434,435,453,2,3,34,546,4,3,45,56,76,767,56,4,8};
        mergeSort(list1);
        for(int n : list1) {
          System.out.println(n);
        }
    
      }
    }

## 5. 快速排序 ##

### 5.1 算法思想 ###

在数组中选择一个成为主元(pivot)的元素，将数组分为两部分，使得第一部分中的所有元素都小于或等于主元，而第二部分中的所有元素都大于主元。对第一部分递归的应用快速排序算法，然后对第二部分递归的应用快速排序算法。假定将数组的第一个元素选为主元。

### 5.2 时间复杂度 ###

*O*(*n*)=*n*log*n*  O ( n ) = n log ⁡ n   
归并排序在归并两个子数组时需要临时数组，而快速排序不需要额外的数组空间。因此空间效率高于归并排序。

### 5.3 代码清单 ###

package sort;
    /* * 18.7.8 * 快速排序练习，默认方向从小到大 * * 算法思想： * 快排首先将数组第一个元素作为主元，而后将元素分为无序的左右两个数组，左边的小于等于主元，右边的大于主元，如此拆分 * 直到拆分为单个元素为止，此时排序也已经完成。 * * 时间复杂度： * 每次拆分的次数k=log2 n,拆分过程中每次的排序和比较的时间复杂度为2n，忽略常量和非主导项，时间复杂度为O(n)=nlogn * * 空间效率： * 由于归并排序需要临时数组，而快排不需要，所以快排的空间效率较高 * */
    public class QuickSort {
      public static void quickSort(int[] list) {
        quickSort(0, list.length - 1, list);
      }
    
      //将原始数组不断细分，每次得到左右两个分别小于等于和大于主元的数组
      //同时得到主元的索引
      public static void quickSort(int first, int last, int[] list) {
        if(last>first) {
          //函数内部进行排序
          int pivotIndex = partition(first,last,list);     
          //递归调用
          quickSort(first,pivotIndex - 1,list);
          quickSort(pivotIndex + 1,last,list);
        }
      }
    
      //计算主元的索引
      public static int partition(int first, int last, int[] list) {
        int pivot = list[first];
        int low = first + 1;
        int high = last;
    
        while(low < high) {
    
          //注意这里下面两个循环都用了<=，最终会得到low=high + 1，即high代表值小于等于pivot的分界线
          while(low <= high && list[low] <= pivot) {
            low++;
          }
    
          while(low <= high && list[high] > pivot) {
            high--;
          }
    
          //if判断确保了他们在数组范围内部
          if(high > low) {
            int temp = list[high];
            list[high] = list[low];
            list[low] = temp;
          }
        }
    
        //确保list[high]一定比pivot小，此处的high数值已经和low对调了
        while(high > first && list[high] >= pivot) {
          high--;
        }
    
        //当pivot>list[high]时，说明有小于pivot的值，要么pivot在中间，要么都比pivot小
        //得到的list[high]是比pivot小的里面最大的值
        //如果为false时说明pivot比所有值都小
        if(pivot > list[high]) {
          list[first] = list[high];
          list[high] = pivot;
          return high;
        } else {
          return first;
        }
      }
    
      public static void main(String[] args) {
        int[] list1= {
       2,3,2,5,6,1,-2,3,14,12};
        quickSort(list1);
        for(int i = 0; i < list1.length; i++) {
          System.out.println(list1[i]);
        }
      }
    }

## 6. 堆排序 ##

### 6.1 算法思想 ###

堆排序使用的是二插堆。它首先将所有的元素添加添加到一个堆上，然后不断移除最大的元素以获得一个排好序的线性表。所谓二插堆，是一棵完全二叉树，如果一个二叉树的每一层都是满的，或者最后一层可以不填满并且最后一层的叶子都是靠左放置的，那么这棵二叉树就是完全的(complete)。  
二插堆(binary heap)是具有以下属性的二叉树：

*  形状属性：是一棵完全二叉树
 *  堆属性：每个节点大于或等于他的任意一个孩子

### 6.2 堆存储 ###

如果堆的大小是事先知道的，那么可以将堆存储在一个ArrayList或一个数组中。对于位置i处的节点，他的左子节点在2i+1处，右子节点在2i+2处，而他的父节点在(i-1)/2处。

### 6.3 添加新的节点 ###

伪代码如下

将最后一个节点当作当前节点；
    while(当前节点大于他的父节点){ 将当前节点与父节点互换； 现在当前节点往上面进了一个层次； }

### 6.4 删除根节点 ###

伪代码如下

用最后一个节点替换跟节点；
    让根节点成为当前节点；
    while(当前节点具有子节点且当前节点小于其子节点){ 当前节点与较大的自节点互换位置； 当前节点向下一层； }

### 6.5 时间复杂度 ###

*O*(*n*)=*n*log*n*  O ( n ) = n log ⁡ n   
向堆中添加一个新元素最多需要h步，建立一个包含n个元素的数组的初始堆需要O(nlogn)时间，从堆中删除根结点后重建的时间也需要O(nlogn)时间，所以由堆产生一个有序数组需要的总时间为O(nlogn)。  
堆排序不需要额外的数组空间，所以堆排序的空间效率高于归并排序。

## 7. 总结 ##

### 7.1 关键术语 ###

bubble sort(冒泡排序)  
heap sort(堆排序)  
bucket sort(桶排序)  
height of a heap(堆的高度)  
complete binary tree(完全二叉树)  
merge sort(归并排序)  
external sort(外部排序)  
quick sort(快速排序)  
heap(堆)  
radix sort(基数排序)

### 7.2 小结 ###

1.  选择排序、插入排序、冒泡排序和快速排序的最差时间复杂度为*O*(*n*2)  O ( n 2 ) 
2.  归并排序的平均情况和最差情况的复杂度为*O*(*n**l**o**g**n*)  O ( n l o g n ) 。快速排序的平均时间也是O(nlogn)。
3.  堆排序的时间复杂度为O(nlogn)
4.  可以使用归并排序的变体，称为外部排序，对外部的文件中的大型数据进行排序。