91资源网

首页>经典在线>技术在线

java快速排序、归并排序详细讲解

2019-06-19 11:06:16 | 查看次数 65 | 分类: 经典在线>技术在线 文章来源:来源:http://www.ifx666.cn

摘要内容:java快速排序、归并排序详细讲解

Java快速排序和归并排序详解

快速排序

概述

快速排序算法借鉴的是二叉树前序遍历的思想,最终对数组进行排序。

优点:

对于数据量比较大的数组排序,由于采用的具有二叉树二分的思想,故排序速度比较快

局限

只适用于顺序存储结构的数据排序(数组 ,ArrayList等),不适用于链式的数据结构

算法实现思路

一.将目标数组转化为这样一个数组。数组中的某个位置左边的所有数据都比该位置的数据小,该位置右边的数据都比该位置数据大。

实现思路:

1.取出数组第0个数据
 
 
2.从数组最右边开始遍历,如果遍历位置的数据比第0个位置的数据小,将该位置的数据赋值给左边指针停留下的位置。
 

3.改变遍历方向,从左边开始开始遍历,如果发现左边的数据比第0个位置的数据大,将该位置的数据赋值给2步骤停留下来的位置,并变换方向。

 

4.循环2、3步骤直到左右遍历到的下标重合
5.将取出的第0个位置的值赋值给循环结束后左右指针停留下的位置

二. 借鉴前序遍历的思路,递归,最终完成排序。

代码实现


 1 private void quickSort(int[] array, int start, int end) {
 2         if (start >= end) {
 3             return;
 4         }
 5         int key = array[start];
 6         int left = start;
 7         int right = end;
 8         boolean direction = true;
 9         L1:
10         while (left < right) {
11             if (direction) {
12                 for (int i = right; i > left; i--) {
13                     if (array[i] < key) {
14                         array[left++] = array[i];
15                         right = i;
16                         direction = !direction;
17                         continue L1;
18                     }
19                 }
20                 right = left;
21             } else {
22                 for (int i = left; i < right; i++) {
23                     if (array[i] > key) {
24                         array[right--] = array[i];
25                         left = i;
26                         direction = !direction;
27                         continue L1;
28                     }
29                 }
30                 left = right;
31             }
32         }
33         array[left] = key;
34         quickSort(array, start, left - 1);
35         quickSort(array, left + 1, end);
36 
37     }

结果测试


1  @Test
2     public void testQuickSort() {
3         int[] array = new int[]{1, 3, 4, 10, 2, 5, 6, 9, 7, 8};
4         quickSort(array, 0, array.length - 1);
5         for (int i = 0; i < array.length; i++) {
6             System.out.println(array[i]);
7         }
8     }

结果打印

 1 1
 2 2
 3 3
 4 4
 5 5
 6 6
 7 7
 8 8
 9 9
10 10

归并排序

概述

归并排序与快速排序相同,同样是借鉴二叉树的思想,时间复杂度O(n),与快速排序一样是大量数据排序的最优方式之一。

思路分析

归并排序是将目标数组分成左右两个数组,左右两个数组必须是有序的,然后对这两个数组合并从而实现排序。对于任意的数组都可以将所有的数据分成若干个数组,每个数组中都只有一个元素,然后两两合并。(因此,归并排序的内存开销会比快速排序多)

代码实现

 1   private void mergeSort(int[] array, int left, int right) {
 2         if (left >= right) {
 3             return;
 4         }
 5         int mid = (left + right) >> 1;
 6         mergeSort(array, left, mid);
 7         mergeSort(array, mid + 1, right);
 8         merge(array, left, mid + 1, right);
 9     }
10 
11     private void merge(int[] array, int left, int mid, int right) {
12         int leftSize = mid - left;
13         int rightSize = right - mid + 1;
14         int[] leftArray = new int[leftSize];
15         int[] rightArray = new int[rightSize];
16         System.arraycopy(array, left, leftArray, 0, leftSize);
17         System.arraycopy(array, mid, rightArray, 0, rightSize);
18         int index=left;
19         int leftIndex = 0;
20         int rightIndex = 0;
21         while (leftIndex<leftSize&&rightIndex<rightSize){
22             if(leftArray[leftIndex]<rightArray[rightIndex]){
23                 array[index++] = leftArray[leftIndex++];
24             }else {
25                 array[index++] = rightArray[rightIndex++];
26             }
27         }
28         while (leftIndex<leftSize){
29             array[index++] = leftArray[leftIndex++];
30         }
31         while (rightIndex<rightSize){
32             array[index++] = rightArray[rightIndex++];
33         }
34     }

测试代码

1  @Test
2     public void testMergeSort() {
3         int[] array = new int[]{1, 3, 4, 10, 2, 5, 6, 9, 7, 8};
4         mergeSort(array, 0, array.length - 1);
5         for (int i = 0; i < array.length; i++) {
6             System.out.println(array[i]);
7         }
8     }

结果打印

1
2
3
4
5
6
7
8
9
10

上一篇: Safe3Web漏洞扫描系统绿色安全版

下一篇: 中文版HBase权威指南

验证码:
评论列表
  • 文章推荐

    09-19 | 查看次数 1174

    《深入理解Spring Cloud与微服务构建》PDF下载

    09-14 | 查看次数 334

    bootstrap tooltip 提示框的样式、提示字体颜...

    09-01 | 查看次数 319

    json字符串与java对象互转,json字符串转化为map...

    08-04 | 查看次数 494

    java面试题及答案---2018核心Java面试问题与解答...

    08-03 | 查看次数 1204

    java面试题及答案---2018核心Java面试问题与解答...

    最新评论
    文章标题:管理和发布文章java cms

    评论内容:能下载吗

    评论时间:2018-12-12 01:30:02

  • 返回顶部
    欢迎投稿
    返回底部