排序总结-常用排序算法Java实现

布满荆棘的人生 2023-05-31 07:59 15阅读 0赞

## 排序总结 ##

稳定

<table> 
 <thead> 
  <tr> 
   <th>sort</th> 
   <th>最差时间</th> 
   <th>最好时间</th> 
   <th>平均时间</th> 
   <th>稳定</th> 
   <th>空间复杂度</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>冒泡排序</td> 
   <td>O(n^2)</td> 
   <td>O(n)</td> 
   <td>O(n^2)</td> 
   <td>稳定</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>插入排序</td> 
   <td>O(n^2)</td> 
   <td>O(n)</td> 
   <td>O(n^2)</td> 
   <td>稳定</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>二叉树排序</td> 
   <td>O(n^2)</td> 
   <td>O(nlogn)</td> 
   <td>O(nlogn)</td> 
   <td>稳定</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td>归并排序l</td> 
   <td>O(nlogn)</td> 
   <td>O(nlogn)</td> 
   <td>O(nlogn)</td> 
   <td>稳定</td> 
   <td>O(n)</td> 
  </tr> 
 </tbody> 
</table>

不稳定

<table> 
 <thead> 
  <tr> 
   <th>sort</th> 
   <th>最差时间</th> 
   <th>最好时间</th> 
   <th>平均时间</th> 
   <th>稳定</th> 
   <th>空间复杂度</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>选择排序</td> 
   <td>O(n^2)</td> 
   <td>O(n^2)</td> 
   <td>O(n^2)</td> 
   <td>不稳定</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>快排</td> 
   <td>O(n^2)</td> 
   <td>O(nlogn)</td> 
   <td>O(nlogn)</td> 
   <td>不稳定</td> 
   <td>O(logn~ O(n))</td> 
  </tr> 
  <tr> 
   <td>堆排序</td> 
   <td>O(nlogn)</td> 
   <td>O(nlogn)</td> 
   <td>O(nlogn)</td> 
   <td>不稳定</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>希尔排序</td> 
   <td>O(n^2)</td> 
   <td></td> 
   <td></td> 
   <td>不稳定</td> 
   <td>O(1)</td> 
  </tr> 
 </tbody> 
</table>

## 冒泡排序(Bubble Sort) ##

它是一种较简单的排序算法。它会遍历若干次要排序的数列，每次遍历时，它都会从前往后依次的比较相邻两个数的大小；如果前者比后者大，则交换它们的位置。这样，一次遍历之后，最大的元素就在数列的末尾！采用相同的方法再次遍历时，第二大的元素就被排列在最大元素之前。重复此操作，直到整个数列都有序为止！  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqY2phdmE_size_16_color_FFFFFF_t_70]

/* * a -- 待排序的数组 * n -- 数组的长度 */
    public static void bubbleSort(int[] a, int n) { 
        int i,
        j;
        for (i = n - 1; i > 0; i--) { 
            // 将a[0...i]中最大的数据放在末尾
            for (j = 0; j < i; j++) { 
                if (a[j] > a[j + 1]) { 
                    // 交换a[j]和a[j+1]
                    int tmp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = tmp;
                }
            }
        }
    }
    
    
    运行：
    int[] a = { 20,40,30,10,60,50,70};
    String aa = "冒泡排序";
    bubbleSort(a, a.length);
    System.out.print(aa);
    for (int d: a) { 
        System.out.print(d + ",");
    }

选择排序和插入排序都是在冒泡基础上的演进：  
选择排序：选出最小的值放入列表，选完即可  
直接插入排序：左侧为有序队列，从右侧遍历的数字在放入左侧有序队列时排序插入。

直接插入排序(Straight Insertion Sort)

/** * @param * a -- 待排序的数组 * n -- 数组的长度 */
    public static void insertSort(int[] a, int n) { 
        int i,j,k;
        for (i = 1; i < n; i++) { 
        	//a[i]为右侧遍历出的待插数据
            //在有序队列a[0,i]中为a[i]在前面的a[0...i-1]有序区间中找一个合适的位置
            for (j = i - 1; j >= 0; j--) if (a[j] < a[i]) break;//从大到小找到比i小的值j即可终止
            //如找到了一个合适的位置, 把整个数组下标大于j的值都往后移动一个空位给i使用
            if (j != i - 1) { 
                //将比a[i]大的数据向后移
                int temp = a[i];
                for (k = i - 1; k > j; k--) a[k + 1] = a[k];
                //将a[i]放到正确位置上
                a[k + 1] = temp;
            }
        }
    }

和冒泡的规则相同，双重for循环找到最最小值

## 快速排序(Quick Sort) ##

使用分治法策略  
它的基本思想是：选择一个基准数，通过一趟排序将要排序的数据分割成独立的两部分；其中一部分的所有数据都比另外一部分的所有数据都要小。然后，再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

快速排序流程：  
1.从数列中挑出一个基准值放入x。  
2.将所有比基准值小的摆放在基准前面，所有比基准值大的摆在基准的后面(相同的数可以到任一边)；在这个分区退出之后，该基准就处于数列的中间位置（把x赋值给中间值，完成一轮互换）。  
3.递归地把"基准值前面的子数列"和"基准值后面的子数列"进行排序。

图文介绍  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqY2phdmE_size_16_color_FFFFFF_t_70 1]

/** * * 参数说明： * a -- 待排序的数组 * l -- 数组的左边界(例如，从起始位置开始排序，则l=0) * r -- 数组的右边界(例如，排序截至到数组末尾，则r=a.length-1) */
    public static void quickSort(int[] a, int l, int r) { 
        if (l < r) { 
            int i,j, x;
            i = l;
            j = r;
            x = a[i];
            while (i < j) { 
                while (i < j && a[j] > x) j--; // 从右向左找第一个小于x的数
                if (i < j) a[i++] = a[j];
                while (i < j && a[i] < x) i++; // 从左向右找第一个大于x的数
                if (i < j) a[j--] = a[i];
            }
            a[i] = x;//最后把基准值赋值给中间值，完成一轮替换
             /* 递归调用 */
            quickSort(a, l, i - 1);//把中间值左侧数据排序
            quickSort(a, i + 1, r);//右侧数据排序
            /* 递归调用 */
        }
    }
    
    
    //运行
     String aa = "快速排序";
     quickSort(a,0,a.length-1);
     System.out.print(aa);
     for (int d : a) { 
     System.out.print(d+",");
     }

## 希尔排序shell sort ##

希尔(Shell)排序又称为缩小增量排序，它是一种插入排序。它是直接插入排序算法的一种威力加强版。该方法因DL．Shell于1959年提出而得名。

希尔排序的基本思想是：  
1.把记录按步长 gap 分组，对每组记录采用直接插入排序方法进行排序。  
2.随着步长逐渐减小，所分成的组包含的记录越来越多，当步长的值减小到 1 时，整个数据合成为一组，构成一组有序记录，则完成排序。

看图配合步骤讲解，第一次gap=5,每隔gap个元素为一组比大小；gap不断对折，直到gap=1完成排序。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqY2phdmE_size_16_color_FFFFFF_t_70 2]  
初始时，有一个大小为 10 的无序序列。

在第一趟排序中，我们不妨设 gap1 = N / 2 = 5，即相隔距离为 5 的元素组成一组，可以分为 5 组。接下来，按照直接插入排序的方法对每个组进行排序。

在第二趟排序中，我们把上次的 gap 缩小一半，即 gap2 = gap1 / 2 = 2 (取整数)。这样每相隔距离为 2 的元素组成一组，可以分为 2 组。按照直接插入排序的方法对每个组进行排序。

在第三趟排序中，再次把 gap 缩小一半，即gap3 = gap2 / 2 = 1。这样相隔距离为 1 的元素组成一组，即只有一组。按照直接插入排序的方法对每个组进行排序。此时，排序已经结束。

需要注意一下的是，图中有两个相等数值的元素 5 和 5 。我们可以清楚的看到，在排序过程中，两个元素位置交换了。

所以，希尔排序是不稳定的算法。

/** * 希尔排序 * @param list */
     public static void shellSort(int[] a) { 
    	 int gap = a.length / 2; //初始对折=步长
    	 while (1 <= gap) { 
    		 // 把距离为 gap 的元素编为一个组，扫描所有组
    		 for (int i = gap; i < a.length; i++) { 
    			 int j = 0;
    			 int temp = a[i];
    			 // 对距离为 gap 的元素组进行排序,每隔gap个为一组对比大小
    			 for (j = i - gap; j >= 0 && temp < a[j]; j = j - gap) { 
    			 	a[j + gap] = a[j];
    			 }
    			 a[j + gap] = temp;
    		 }
    		 System.out.format("gap = %d:\t", gap);
    		 printAll(a);
    		 gap = gap / 2; // 减小增量
    	 }
    }
    	 // 打印完整序列
     public static void printAll(int[] a) { 
    	 for (int value : a) { 
    	 System.out.print(value + "\t");
    	 }
    	 System.out.println();
     }

## 归并排序 ##

基本思想  
归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

分而治之  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqY2phdmE_size_16_color_FFFFFF_t_70 3]  
和希尔排序的思想视乎有些相似，都是对折分组  
可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程，递归深度为log2n。

每个小组最后都要面对的一步：**合并相邻有序子序列**  
再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将\[4,5,7,8\]和\[1,2,3,6\]两个已经有序的子序列，合并为最终序列\[1,2,3,4,5,6,7,8\]，来看下实现步骤。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqY2phdmE_size_16_color_FFFFFF_t_70 4]  
思路：创建一个两个数组长度之和的临时数组temp，两个数组对比，谁小就放入temp中。对比完成

public class MergeSort { 
     public static void main(String []args){ 
    	 int []arr = { 9,8,7,6,5,4,3,2,1};
    	 sort(arr);
    	 System.out.println(Arrays.toString(arr));
     }
    
     public static void sort(int []arr){ 
    	 int []temp = new int[arr.length];
    	 //在排序前，先建好一个长度等于原数组长度的临时数组，
    	 //避免递归中频繁开辟空间
    	 sort(arr,0,arr.length-1,temp);
     }
     
     private static void sort(int[] arr,int left,int right,int []temp){ 
    	 if(left<right){ 
    		 int mid = (left+right)/2;
    		 sort(arr,left,mid,temp);//递归调用：左边归并排序，使得左子序列有序
    		 sort(arr,mid+1,right,temp);//递归调用：右边归并排序，使得右子序列有序
    		 merge(arr,left,mid,right,temp);//将两个有序子数组合并操作
    	 }
     }
     private static void merge(int[] arr,int left,int mid,int right,int[] temp){ 
    	 int i = left;//左序列指针
    	 int j = mid+1;//右序列指针
    	 int t = 0;//临时数组指针
    	 while (i<=mid && j<=right){ 
    		 if(arr[i]<=arr[j]){ 
    		 	temp[t++] = arr[i++];
    		 }else { 
    			 temp[t++] = arr[j++];
    		 }
    	 }
    	 while(i<=mid){ //将左边剩余元素填充进temp中
    	 temp[t++] = arr[i++];
    	 }
    	 while(j<=right){ //将右序列剩余元素填充进temp中
    	 temp[t++] = arr[j++];
    	 }
    	 t = 0;
    	 //将temp中的元素全部拷贝到原数组中
    	 while(left <= right){ 
    	 arr[left++] = temp[t++];
    	 }
     }
    }

## 堆排序 ##

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。

*  完全二叉树： 除了最后一层之外的其他每一层都被完全填充，并且所有结点都保持向左对齐。
 *  满二叉树：除了叶子结点之外的每一个结点都有两个孩子，每一层(当然包含最后一层)都被完全填充。
 *  完满二叉树：除了叶子结点之外的每一个结点都有两个孩子结点。

完全二叉树(Complete Binary Tree)：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqY2phdmE_size_16_color_FFFFFF_t_70 5]  
满二叉树(Perfect Binary Tree)：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqY2phdmE_size_16_color_FFFFFF_t_70 6]  
完满二叉树(Full Binary Tree)：  
![在这里插入图片描述][20191024183201965.png]  
参考资料：  
http://www.cnblogs.com/idorax/p/6441043.html

堆排序是将数据看成是完全二叉树、根据完全二叉树的特性来进行排序的一种算法  
**最大堆**要求节点的元素都要不小于其孩子，  
**最小堆**要求节点元素都不大于其左右孩子  
处于最大堆的根节点的元素一定是这个堆中的最大值

完全二叉树有个特性：  
左边子节点位置 = 当前父节点的两倍 + 1  
右边子节点位置 = 当前父节点的两倍 + 2

节点的关系和节点编号和数组下标对象的下标关系：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqY2phdmE_size_16_color_FFFFFF_t_70 7]

**排序过程**  
第一步：先n个元素的无序序列，构建成大顶堆  
第二步：将根节点与最后一个元素交换位置，（将最大元素"沉"到数组末端）  
第三步：交换过后可能不再满足大顶堆的条件，所以需要将剩下的n-1个元素重新构建成大顶堆  
第四步：重复第二步、第三步直到整个数组排序完成  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqY2phdmE_size_16_color_FFFFFF_t_70 8]

/** * 建堆 * * @param arrays 看作是完全二叉树 * @param currentRootNode 当前父节点位置 * @param size 节点总数 */
        public static void heapify(int[] arrays, int currentRootNode, int size) { 
    
           if (currentRootNode < size) { 
               //左子树和右字数的位置
               int left = 2 * currentRootNode + 1;
               int right = 2 * currentRootNode + 2;
    
               //把当前父节点位置看成是最大的
               int max = currentRootNode;
    
               if (left < size) { 
                   //如果比当前根元素要大，记录它的位置
                   if (arrays[max] < arrays[left]) { 
                       max = left;
                   }
               }
               if (right < size) { 
                   //如果比当前根元素要大，记录它的位置
                   if (arrays[max] < arrays[right]) { 
                       max = right;
                   }
               }
               //如果最大的不是根元素位置，那么就交换
               if (max != currentRootNode) { 
                   int temp = arrays[max];
                   arrays[max] = arrays[currentRootNode];
                   arrays[currentRootNode] = temp;
    
                   //继续比较，直到完成一次建堆
                   heapify(arrays, max, size);
               }
           }
       }
    
    
    
      /** * 完成一次建堆，最大值在堆的顶部(根节点) */
       public static void maxHeapify(int[] arrays, int size) { 
    
           // 从数组的尾部开始，直到第一个元素(角标为0)
           for (int i = size - 1; i >= 0; i--) { 
               heapify(arrays, i, size);
           }
    
       }
    
    	//堆排序入口
    public static void heapSort(int[] arrays) { 
    	for (int i = 0; i < arrays.length; i++) { 
            //每次建堆就可以排除一个元素了
            maxHeapify(arrays, arrays.length - i);
            //把顶部最大值放到数组最后面
            int temp = arrays[0];
            arrays[0] = arrays[(arrays.length - 1) - i];
            arrays[(arrays.length - 1) - i] = temp;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqY2phdmE_size_16_color_FFFFFF_t_70]: /images/20230531/71ef0f81c8fe4bc49fedb3eeb83a2f96.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqY2phdmE_size_16_color_FFFFFF_t_70 1]: /images/20230531/017d148e49fd4f87ac12f7e820fc4434.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqY2phdmE_size_16_color_FFFFFF_t_70 2]: /images/20230531/0a2d562657ea4ebc8438c83b0f5f8924.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqY2phdmE_size_16_color_FFFFFF_t_70 3]: /images/20230531/e283f25403864b26a90f8316ff7aaf93.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqY2phdmE_size_16_color_FFFFFF_t_70 4]: /images/20230531/5de3192f1f784c37a1fe938dd504a091.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqY2phdmE_size_16_color_FFFFFF_t_70 5]: /images/20230531/7dc65007a20744aead21ddcc5a344538.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqY2phdmE_size_16_color_FFFFFF_t_70 6]: /images/20230531/15c76b3f7df840ef98f29f70e8b9039c.png
[20191024183201965.png]: /images/20230531/5661b1c78c834ee3af506ba8e0c16c92.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqY2phdmE_size_16_color_FFFFFF_t_70 7]: /images/20230531/39dbeda34501442299982f365f5d61a5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqY2phdmE_size_16_color_FFFFFF_t_70 8]: /images/20230531/29e64da6ccb04e65828f5460dd557d42.png