X

曜彤.手记

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

吉 ICP 备10004938号

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


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

一、冒泡排序:

冒泡排序主要思路是依次比较相邻的两个元素,并将这两个元素按照所需要的升序或者降序进行交换排列(例如 {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);
}


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