大话数据结构-第9章 排序- 高飞网

第9章 排序

2016-03-10 00:06:43.0

冒泡排序

冒泡排序(Bubble Sort)是一种交换排序,基本思想是:两两比较相邻记录的关键字,如果反序则交换,直到没有反序的记录为止。

// 冒泡排序
public static void bubbleSort(int[] arr) {
    int len = arr.length;
    for (int i = 0; i < len; i++) {
        int cnt = 0;
        for (int j = len - 1; j > i; j--) {
            if (arr[j] < arr[j - 1]) {// 从后往前,将小的数往上冒泡
                swap(arr, j, j - 1);
                cnt++;
            }
        }
        if (cnt == 0) {// 如果这一趟没发生交换,则排序完成
            break;
        }
    }
}

时间复杂度:n(n-1)/2 = n2-2n = O(n2)


简单选择排序

简单选择排序法(Simple Selection Sort)是通过n-i次关键字间的比较,从n-i+1个记录中选择关键字最小的记录,并和第i(1<=i<=n)个记录交换。

// 简单选择排序
public static void selectSort(int[] arr) {
    int len = arr.length;
    for (int i = 0; i < len; i++) {
        int min = i;
        for (int j = i + 1; j < len; j++) {// 比较i和i以后的数据,找出最小数据
            if (arr[min] > arr[j]) {
                min = j;
            }
        }
        if (min != i) {// 将最小数据放到前面
            swap(arr, i, min);
        }
    }
}

时间复杂度:n(n-1)/2 = O(n2),较冒泡略优,因为它减少了交换元素的次数。


直接插入排序

直接插入排序(Straight Insertion Sort)的基本操作是将一个记录插入到已经排好序的有序表中,从而得到一个新的,记录数增1的有序表。

// 插入排序
public static void insertSort(int[] arr) {
    int len = arr.length;
    for (int i = 1; i < len; i++) {// 把数组的第1个元素作为一个有序子数组,因此从第二个元素开始与子数组中的元素进行比较
        if (arr[i] < arr[i - 1]) {// 如果某元素比有序子数组末尾小,则说明需要将该元素插入到子表的适当位置
            int e = arr[i];// 把被比较的arr[i]保存到哨兵缓存中
            int j = i - 1;
            for (; j >= 0; j--) {// 从末尾往前搜索
                if (e < arr[j]) {// 只要比e大,就往后移
                    arr[j + 1] = arr[j];
                } else {// 否则就找到位置了
                    break;
                }
            }
            arr[j + 1] = e;// 将哨兵插入到该位置
        }
    }
}

时间复杂度:n2/4 = O(n2),优于冒泡和选择排序。

适用记录少,而且基本是有序的。