算法--排序

目录

• 排序
  • 常用函数
  • 选择排序
    • 原理
    • 模拟
    • 时间复杂度：
  • 代码
  • 插入排序
    • 时间复杂度：
  • 代码
  • 希尔排序
  • 原理
  • 代码

*** 注:默认排序完成顺序为从小到大 ***

排序

常用函数

public class Example {
    public static boolean less(Comparable a, Comparable b) {  //a<b?
        return a.compareTo(b) < 0;
    }

    public static void exch(Comparable[] a, int i, int j) {   // exch=exchange
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

选择排序

原理

有一个数组Array长度为N，从Array[0]-Array[N]中选出最小的和Array[0]交换，然后从Array[1]-Array[N]中选出最小的和Array[1]交换。

模拟

时间复杂度：

最优情况下即开始时顺序已排列好。
需要比较N+(N-1)+(N-2)+........+0;
交换0次
最坏情况下
需要比较N+(N-1)+(N-2)+........+0
交换N-1次

代码

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

插入排序

时间复杂度：

最优情况下即开始时顺序已排列好。
需要
比较N-1次
交换0次
最坏情况下即开始时为从大到小排列
需要
比较1+2+3+4+......+N-1次
交换1+2+3+4+......+N-1次
例:
5 4 3 2 1   比较    交换
4 5          1       1

4 3 5
3 4 5        2       2

4 3 2 5
4 2 3 5
2 3 4 5      3       3
   。
   。
   。
   。

代码

public static void Insertion_Sort(Comparable[] a) {
        int N = a.length;
        for (int i = 1; i < N; i++)
            for (int j = i; j > 0 && less(a[j], a[j - 1]); j--)
                exch(a, j, j - 1);
    }

希尔排序

原理

代码

public static void Shell_Sort(Comparable[] a) {
        int N = a.length;
        int h = 1;
        while (h < N / 3) h = h * 3 + 1;
        while (h >= 1) {
            for (int i = h; i < N; i++)
                for (int j = i; j >= h && less(a[j], a[j - h]); j -= h)
                    exch(a, j, j - h);
            h = h / 3;
        }
    }