文档开发者中心
我的

程序员那些必须掌握的排序算法(中)

接着上一篇的排序算法,我们废话不多说,直接进入主题。


1.快速排序


快速排序(Quicksort)是对冒泡排序的一种改进。


快速排序由C. A. R. Hoare在1960年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。


演示:

在这里插入图片描述


代码如下:


public static void quickSort(int[] arr, int left, int right) {

 int l = left;// 左下标

 int r = right;// 右下标

 int pivot = arr[(left + right) / 2];// 找到中间的值

 // 将比pivot小的值放在其左边,比pivot大的值放在其右边

 while (l < r) {

  // 在pivot左边寻找,直至找到大于等于pivot的值才退出

  while (arr[l] < pivot) {

   l += 1;// 将l右移一位

  }

  // 在pivot右边寻找,直至找到小于等于pivot的值才退出

  while (arr[r] > pivot) {

   r -= 1;// 将r左移一位

  }

  if (l >= r) {

   // 左右下标重合,寻找完毕,退出循环

   break;

  }

  // 交换元素

  int temp = arr[l];

  arr[l] = arr[r];

  arr[r] = temp;


  //倘若发现值相等的情况,则没有比较的必要,直接移动下标即可

 

  // 如果交换完后,发现arr[l]==pivot,此时应将r左移一位

  if (arr[l] == pivot) {

   r -= 1;

  }

  // 如果交换完后,发现arr[r]==pivot,此时应将l右移一位

  if (arr[r] == pivot) {

   l += 1;

  }

 }

 // 如果l==r,要把这两个下标错开,否则会出现无限递归,导致栈溢出的情况

 if (l == r) {

  l += 1;

  r -= 1;

 }

 // 向左递归

 if (left < r) {

  quickSort(arr, left, r);

 }

 // 向右递归

 if (right > l) {

  quickSort(arr, l, right);

 }

}


测试代码:


public static void main(String[] args) {

 int[] arr = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };

 quickSort(arr, 0, arr.length - 1);

 System.out.println(Arrays.toString(arr));

}


运行结果:


[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]


快速排序的实现原理很简单,就是将原数组分成两部分,然后以中间值为标准,比它小的就放其左边,比它大的就放其右边,然后在左右两边又以相同的方式继续排序。


所以在代码实现过程中,首先要创建两个移动的变量,一个从最左边开始往右移动,一个从最右边开始往左移动,通过这两个变量来遍历左右两部分的元素。当发现左边有大于中间数的元素,右边有小于中间数的元素,此时就进行交换。当两个变量重合也就是相等的时候遍历结束,然后左右两部分作递归处理。


2.归并排序


归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。


演示:


在这里插入图片描述



归并排序使用了一种分治思想,分治思想的意思就是’分而治之',就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单地直接求解。


通过这个动图来看的话,相信很多人都一脸懵,没关系,我们通过静态图来分析一下:

在这里插入图片描述

假设现在有一个待排序的序列,[5,2,4,7,1,3,2,2],那么我们就需要将该序列进行分治,先将其分成两份:[5,2,4,7]和[1,3,2,2],再将这两份分别分成两份:[5,2]和[4,7];[1,3]和[2,2],最后将这四部分再次分别分为两份,最后就将整个序列分为了八份。需要注意的是,在分的过程中,不需要遵循任何规则,关键在于归并,归并的过程中便实现了元素的排序。


代码如下:


public static void mergeSort(int[] arr, int left, int right, int[] temp) {

 // 分解

 if (left < right) {

  int mid = (left + right) / 2;// 中间索引

  // 向左递归进行分解

  mergeSort(arr, left, mid, temp);

  // 向右递归进行分解

  mergeSort(arr, mid + 1, right, temp);// mid + 1,中间位置的后一个位置才是右边序列的开始位置

  // 每分解一轮便合并一轮

  merge(arr, left, right, mid, temp);

 }

}


/**

* 合并的方法

*

* @param arr   待排序的数组

* @param left  左边有序序列的初始索引

* @param right 中间索引

* @param mid   右边有序序列的初始索引

* @param temp  做中转的数组

*/

public static void merge(int[] arr, int left, int right, int mid, int[] temp) {

 int i = left; // 初始化i,左边有序序列的初始索引

 int j = mid + 1;// 初始化j,右边有序序列的初始索引(右边有序序列的初始位置即为中间位置的后一个位置)

 int t = 0;// 指向temp数组的当前索引,初始为0

 // 先把左右两边的数据(已经有序)按规则填充到temp数组

 // 直到左右两边的有序序列,有一边处理完成为止

 while (i <= mid && j <= right) {

  // 如果左边有序序列的当前元素小于或等于右边有序序列的当前元素,就将左边的元素填充到temp数组中

  if (arr[i] <= arr[j]) {

   temp[t] = arr[i];

   t++;// 索引后移

   i++;// i后移

  } else {

   // 反之,将右边有序序列的当前元素填充到temp数组中

   temp[t] = arr[j];

   t++;// 索引后移

   j++;// j后移

  }

 }

 // 把有剩余数据的一边的元素填充到temp中

 while (i <= mid) {

  // 此时说明左边序列还有剩余元素

  // 全部填充到temp数组

  temp[t] = arr[i];

  t++;

  i++;

 }

 while (j <= right) {

  // 此时说明左边序列还有剩余元素

  // 全部填充到temp数组

  temp[t] = arr[j];

  t++;

  j++;

 }

 // 将temp数组的元素复制到原数组

 t = 0;

 int tempLeft = left;

 while (tempLeft <= right) {

  arr[tempLeft] = temp[t];

  t++;

  tempLeft++;

 }

}


关于归并排序的算法思想确实比较绕,所以我也在代码中写了很多注释。


我们先来测试一下:


public static void main(String[] args) {

 int[] arr = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };

 int[] temp = new int[arr.length];

 mergeSort(arr, 0, arr.length - 1, temp);

 System.out.println(Arrays.toString(arr));

}


运行结果:


[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]


来分析一下吧,对于该排序算法,有两个部分组成,分解和合并。首先讲讲分解,在前面也说到了,我们需要将待排序的序列不停地进行分解,通过两个索引变量控制,一个初始索引,一个结尾索引。只有当两索引重合才结束分解。此时序列被分解成了十五个小份,这样分解工作就完成了。接下来是合并,合并操作也是最麻烦的,也是通过两个索引变量i,j。开始i在左边序列的第一个位置,j在右边序列的第一个位置,然后就是寻找左右两个序列中的最小值,放到新序列中,这时可能会出现一边的元素都放置完毕了,而另外一边还存在元素,此时只需将剩余的元素按顺序放进新序列即可,因为这时左右两边的序列已经是有序的了,最后将新序列复制到旧序列。这里也特别需要注意,因为合并的过程是分步的,而并非一次合并完成,所以数组的索引是在不断变化的。


自己手动画了个图,左右两个箭头就是索引变量i,j,当i所指的元素也就是1和j所指的元素也就是2进行比较,发现1小,就将1放到新数组的第一个位置,此时应该将i和新数组的索引都右移一位,然后继续比较,以此类推,相信这样大家应该能理解了吧。

在这里插入图片描述


————————————————

版权声明:本文为CSDN博主「~wangweijun」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。

原文链接:

点赞
收藏
回复
3
分享
举报
浏览385 发布于2019-10-24 09:14未知归属地
全部评论
最多点赞
最新发布
最早发布

这论坛的答复还蛮快的


3楼回复于2019-10-26 05:38 未知归属地

关联阅读:程序员那些必须掌握的排序算法(下)

2楼回复于2019-10-24 09:20 未知归属地

关联阅读:程序员那些必须掌握的排序算法(上)

1楼回复于2019-10-24 09:19 未知归属地
写回答
新增插入模板功能
一键使用模板,快速填写内容,轻松发帖~
知道了
  • 为了保障您的信息安全,请勿上传您的敏感个人信息(如您的密码等信息)和您的敏感资产信息(如关键源代码、签名私钥、调试安装包、业务日志等信息),且您需自行承担由此产生的信息泄露等安全风险。
  • 如您发布的内容为转载内容,请注明内容来源。

我要发帖子

了解社区公约,与您携手共创和谐专业的开发者社区。