• 售前

  • 售后

热门帖子
入门百科

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

[复制链接]
做农告根乎 显示全部楼层 发表于 2022-1-14 10:42:19 |阅读模式 打印 上一主题 下一主题

1.直接插入排序

1.1 动图演示


1.2 插入排序的思路:

   

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

  1.     /**
  2.      * 时间复杂度:
  3.      *      最好的情况: O(n)
  4.      *      最坏的情况: O(n^2)
  5.      * 空间复杂度: O(1)
  6.      * @param array
  7.      */
  8.     public static void insertSort(int[] array) {
  9.         for (int i = 1; i < array.length; i++) {
  10.             int j = i - 1;
  11.             int tmp = array[i];
  12.             while (j >= 0) {
  13.                 if (array[j] > tmp) {
  14.                     array[j + 1] = array[j];
  15.                     j--;
  16.                 }else {
  17.                     break;
  18.                 }
  19.             }
  20.             array[j + 1] = tmp;
  21.         }
  22.     }
复制代码
1.4 性能分析

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

2.1 原理

希尔排序法又称缩小增量法。希尔排序法的基本思想是:先选定一个整数gap,把待排序文件中所有记录分成个gap组,所有距离为gap的记录分在同一组内,并对每一组内的记录进行排序。然后,取gap = (gap/3)+1,重复上述分组和排序的工作。当到达gap=1时,所有记录在统一组内排好序。

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

2.2 动图演示


2.3 代码实现:

  1.     /**
  2.      *
  3.       * @param array 排序的数组
  4.      * @param gap 每组的间隔 -> 数组
  5.      */
  6.      public static void shell(int[] array,int gap){
  7.          for (int i = gap; i < array.length ; i++) {
  8.              int tmp = array[i];
  9.              int j = i - gap;
  10.              while(j>=0){
  11.                  if(array[j] > tmp){
  12.                      array[j + gap] = array[j];
  13.                      j -= gap;
  14.                  }else {
  15.                      break;
  16.                  }
  17.              }
  18.              array[j + gap] = tmp;
  19.          }
  20.      }
  21.      public static void shellSort(int[] array){
  22.          int gap = array.length;
  23.          while (gap > 1){
  24.              gap = (gap / 3) + 1;// +1 保证最后一个序列是 1 (除几都行)
  25.              shell(array,gap);
  26.          }
  27.      }
复制代码
2.4 性能分析

时间复杂度(平均)时间复杂度(最坏)时间复杂度(最好)空间复杂度稳定性O(n^1.3)O(n^2)O(n)O(1)不稳定3.直接选择排序

3.1 动图演示


3.2 代码实现:

  1. /**
  2.      * 时间复杂度:
  3.      *      最好: O(n^2)
  4.      *      最坏: O(n^2)
  5.      * 空间复杂度: O(1)
  6.      * 稳定性: 不稳定
  7.      * @param array
  8.      */
  9.     public static void selectSort(int[] array){
  10.         for (int i = 0; i < array.length - 1; i++) {
  11.             for (int j = i + 1; j <array.length ; j++) {
  12.                 if(array[j] < array[i]){
  13.                     int tmp = array[i];
  14.                     array[i] = array[j];
  15.                     array[j] = tmp;
  16.                 }
  17.             }
  18.         }
  19.     }
复制代码
4.3 性能分析

时间复杂度(平均)时间复杂度(最坏)时间复杂度(最好)空间复杂度稳定性O(n * log(n))O(n * log(n))O(n * log(n))O(1)不稳定5.冒泡排序

5.1 动图演示


5.2 代码实现

  1.     public static void siftDown(int[] array,int root, int len){
  2.         int parent = root;
  3.         int child = root * 2 + 1;
  4.         while (child < len){
  5.             if( child+1 < len && array[child] < array[child+1] ){
  6.                 child++;
  7.             }
  8.             //这里child下标就是左右孩子的最大值的下标
  9.             if(array[child] > array[parent]){
  10.                 int tmp = array[child];
  11.                 array[child] = array[parent];
  12.                 array[parent] = tmp;
  13.                 parent = child;
  14.                 child = parent * 2 + 1;
  15.             }else {
  16.                 break;
  17.             }
  18.         }
  19.     }
  20.     public static void createHeap(int[] array){
  21.         for (int i = (array.length - 1 - 1) / 2; i >= 0; i++) {
  22.             siftDown(array,i,array.length);
  23.         }
  24.     }
  25.     public static void heapSort(int[] array){
  26.         createHeap(array);
  27.         int end = array.length - 1;
  28.         while (end > 0){
  29.             int tmp = array[end];
  30.             array[end] = array[0];
  31.             array[0] =tmp;
  32.             siftDown(array,0,end);
  33.             end--;
  34.         }
  35.     }
复制代码
5.3 性能分析

时间复杂度(平均)时间复杂度(最坏)时间复杂度(最好)空间复杂度稳定性O(n^2)O(n^2)O(n)O(1)稳定6.快速排序

6.1 原理


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


6.3 实现方法

6.3.1 Hoare法:


6.3.2 挖坑法:


6.4 代码实现

  1. public static void BubbleSort(int[] array){
  2.         for (int i = 0; i < array.length - 1; i++) {
  3.             boolean flg = false;
  4.             for (int j = 0; j < array.length - 1 - i ; j++) {
  5.                 if(array[j+1] < array[j]){
  6.                     int tmp = array[j];
  7.                     array[j] = array[j+1];
  8.                     array[j+1] = tmp;
  9.                     flg = true;
  10.                 }
  11.             }
  12.             if(!flg){
  13.                 break;
  14.             }
  15.         }
  16.     }
复制代码
6.5 快排优化

6.5.1 三数取中法

  1.     //Hoare法
  2.     public static void swap(int[] array,int i,int j){
  3.         int tmp = array[i];
  4.         array[i] = array[j];
  5.         array[j] = tmp;
  6.     }
  7.     public static int partition1(int[] array,int low,int high) {
  8.         int i = low;
  9.         int tmp = array[low];
  10.         while (low < high){
  11.             while (low < high && array[high] >= tmp){
  12.                 high--;
  13.             }
  14.             while (low < high && array[low] <= tmp){
  15.                 low++;
  16.             }
  17.             swap(array,low,high);
  18.         }
  19.         swap(array,i,low);
  20.         return low;
  21.     }
  22.     //挖坑法
  23.     public static int partition2(int[] array,int low,int high) {
  24.         int tmp = array[low];
  25.         while (low < high){
  26.             while (low < high && array[high] >= tmp){
  27.                 high--;
  28.             }
  29.             array[low] = array[high];
  30.             while (low < high && array[low] <= tmp){
  31.                 low++;
  32.             }
  33.             array[high] = array[low];
  34.         }
  35.         array[low] = tmp;
  36.         return low;
  37.     }
  38.     public static void quick(int[] array,int start,int end){
  39.         if(start >= end) return;
  40.         int pivot = partition1(array,start,end);
  41.         quick(array,start,pivot-1);
  42.         quick(array,pivot+1,end);
  43.     }
  44.     public static void quickSort(int[] array){
  45.         quick(array,0,array.length-1);
  46.     }
复制代码
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 代码实现—递归

[code]    public static void merge(int[] array,int low ,int high ,int mid){        int s1 = low;        int e1 = mid;        int s2 = mid+1;        int e2 = high;        int[] tmp = new int[high - low + 1];        int k = 0;        while (s1

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x

帖子地址: 

回复

使用道具 举报

分享
推广
火星云矿 | 预约S19Pro,享500抵1000!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

草根技术分享(草根吧)是全球知名中文IT技术交流平台,创建于2021年,包含原创博客、精品问答、职业培训、技术社区、资源下载等产品服务,提供原创、优质、完整内容的专业IT技术开发社区。
  • 官方手机版

  • 微信公众号

  • 商务合作