首页 > 代码库 > 排序算法

排序算法

2024-07-10 16:17:49   227人阅读



选择排序

定义：依次选择最小的元素放在相应的位置上
特点：比较次数是 N(N-1)/2  交换次数是 N （each exchange puts an item into its ?nal position, so the number of exchanges is N. Thus, the running time is dominated by the number of compares）；每一次寻找最小元素的过程不会为下一趟的寻找提供额外信息，所以对于一个有序的数组，仍然要花和一个随机数组一样长的时间；选择排序中数组访问是和数组尺寸线性相关的，这是其他排序不具有的。
实现：
public class SelectionSort {

      // This class should not be instantiated.
      private SelectionSort() {
     }

      // ascending order
      public static void sort(Comparable[] a) {
           int N = a.length ;
           for (int i = 0; i < N; i++) {
               int min = i;
               for (int j = i + 1; j < N; j++) {
                    if (less(a[j], a[min]))
                        min = j;
              }
               exch(a, i, min);
               assert isSorted(a, 0, i);
          }
           assert isSorted(a);
     }

      /***********************************************************************
      * Helper sorting functions
      ***********************************************************************/

      // is v < w ?
      private static boolean less(Comparable v, Comparable w) {
           return (v.compareTo(w) < 0);
     }

      // exchange a[i] and a[j]
      private static void exch(Object[] a, int i, int j) {
          Object swap = a[i];
          a[i] = a[j];
          a[j] = swap;
     }

      /***********************************************************************
      * Check if array is sorted - useful for debugging
      ***********************************************************************/
      // is the array a[] sorted?
      private static boolean isSorted(Comparable [] a) {
           return isSorted(a, 0, a. length - 1);
     }

      // is the array sorted from a[lo] to a[ hi]
      private static boolean isSorted(Comparable [] a, int lo, int hi) {
           for (int i = lo + 1; i <= hi; i++)
               if (less(a[i], a[i - 1]))
                    return false ;
           return true ;
     }

      // print array to standard output
      private static void show(Comparable[] a) {
           for (int i = 0; i < a. length; i++) {
              System. out .print(a[i] + " " );
          }
     }

      public static void main(String[] args) {
          Integer[] a = { 10, 45, 0, 8, 7, -34, 20 };
          SelectionSort. sort(a);
           show(a);
     }
}

插入排序

定义：可以联系到扑克牌，每次都是将一个数字插入到一个有序序列的合适位置，为了给其腾出空间，需要后移比他大的元素。
特点：虽然在当前元素（current index）左边都是有序的，但是却不是他们的最终位置；对于一个随机数组，假设每次在插入一个元素时都是移动一半，则#compare=N^2/4，#exchange=N^2/4；最坏情况是每次都是插入到第一个位置（和选择排序一样了）是N^2/2，最好情况是已经有序，只需要比较N-1次。
实现：
public class InsertionSort {
      //其他代码同上
      // ascending order
      public static void sort(Comparable[] a) {
           int N = a.length ;
           for (int i = 0; i < N; i++) {
               for (int j = i; j > 0 && less (a[j], a[j - 1]); j--) {
                    exch(a, j, j - 1);
              }
          }
     }
}


联系
我们