X

曜彤.手记

随手写写,关于互联网技术、产品与创业

算法基础 - 常用排序算法(上)


本文分为上下两篇,主要介绍算法中常用的七种“排序”算法。这七种算法主要是:冒泡排序、快速排序、归并排序、选择排序、堆排序、插入排序和希尔排序。算法问题大部分主要集中在“排序”和“查找”两部分,只有在对基础的排序算法有了深刻了解的基础上,我们才能为进一步学习诸如“动态规划”等高级算法思路打下基础。

一、冒泡排序:

冒泡排序主要思路是依次比较相邻的两个元素,并将这两个元素按照所需要的升序或者降序进行交换排列(例如 {1, 2},按照升序则不用交换,否则按照降序交换两个元素的值,即变为 {2, 1}),每一次完整的循环都会排列好整个数组中的一个元素,若数组含有 N 个元素,则一共需要循环 N-1 次;第一次循环比较 N-1 次,第二次循环比较 N-2 次,依次类推。时间复杂度为 “O(n2)”,总共比较次数 “1 + 2 + … + (n - 1) = (1 + n - 1)(n - 1) / 2 = n(n - 1) / 2”次。Java 实现代码如下所示:

public static int[] bubbleSort(int [] arr, String type) {
    if (arr == null || arr.length == 0) {
        return null; 
    }

    int len = arr.length;
    int temp = 0;

    for (int j = 0; j < len - 1; j++) {
        // 正序,由小到大;每次循环开头位置后移一位,结束位置不变;
        if (type == "ASC") {
            for (int i = j; i < len - 1; i++) {        
                if (arr[i] > arr[i + 1]) {
                    temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                }
            }
        }
        // 逆序,由大到小;每次循环结束位置前移一位,开头位置不变;
        if (type == "DESC") {
            for (int i = 0; i < len - j - 1; i++) {        
                if (arr[i] < arr[i + 1]) {
                    temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                }
            }
        }
    }    
    return arr;
}

二、快速排序:

快速排序是一种高级的排序方法,其思想主要是根据“基准数”将大于或小于“基准数”的数字分别放置到该“基准数”的两侧,然后以同样的方式在上一个“基准数”两侧的子序列中选取下一个“基准数”以同样的方式处理子序列,依次递归处理子序列产生的子序列,直到全部处理完毕。该算法的平均时间复杂度为 “O(NlogN)”,最坏情况下仍可能是相邻的两个数进行了交换,此时的时间复杂度同“冒泡排序”,为 “O(N2)”。Java 实现代码如下所示:

public static void quickSort(int[] arr, int low, int high) {
    if (arr == null || arr.length == 0)
        return;
    if (low >= high)
        return;

    // 选择基准数;
    int middle = low + (high - low) / 2;
    int pivot = arr[middle];

    int i = low;
    int j = high;
    // 开始循环;
    while (i <= j) {
        while (arr[i] < pivot) {
            i++;
        }
        while (arr[j] > pivot) {
            j--;
        }
        if (i <= j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
    }

    // 递归处理子序列;
    if (low < j)
        quickSort(arr, low, j);
    if (high > i)
        quickSort(arr, i, high);
}


这是文章底线,下面是评论
  暂无评论,欢迎勾搭 :)