苏木三少
错的不是你,而是这个世界。

<每天一个> 算法实现之快速排序

快速排序

算法思想:

首先快速排序是一种分而治之的排序算法,它将一个数组分成两个子数组,将两部分独立地排序。

分而治之”( Divide and conquer)方法(又称“分治术”) ,是有效算法设计中普遍采用的一种技术。
所谓“分而治之” 就是把一个复杂的算法问题按一定的“分解”方法分为等价的规模较小的若干部分,然后逐个解决,分别找出各部分的解,把各部分的解组成整个问题的解,这种朴素的思想来源于人们生活与工作的经验,也完全适合于技术领域。诸如软件的体系结构设计、模块化设计都是分而治之的具体表现。

算法实现:

一、快速排序的切分

二、算法的实现框架

实现代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
package algorithm;
import java.util.Scanner;
public class QuickSort {
    public static void sort(Comparable a[]) {
        sort(a, 0, a.length - 1);
    }
    private static boolean less(Comparable v,Comparable w) {
        return v.compareTo(w) < 0;
    }
    private static void exch(Comparable a[],int i,int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    private static int partition(Comparable a[],int lo,int hi) {
        //将数组切分为a[lo..i-1],a[i],a[i+1..hi]
        int i = lo,j = hi +1;
        Comparable v = a[lo];
        while(true)
        {//扫描左右,检查扫描是否结束并交换元素
            while(less(a[++i],v))
                if(i == hi)
                    break;
            while(less(v, a[--j]))
                if(j == lo)
                    break;
            if(i  >= j)
                break;
            exch(a, i, j);
        }
        exch(a, lo, j);//将v = a[j]放入正确的位置
        return j;//a[lo..j-1] <= a[j] <= a[j+1..hi]达成
       
    }
    private static void sort(Comparable a[],int lo,int hi)
    {
        if(hi <= lo) {
            return;
        }
        int j = partition(a, lo, hi);//切分
        sort(a, lo, j-1);//将左半部分a[lo..j-1]排序
        sort(a, j+1,hi);//将右半部分a[j+1..hi]排序
    }

    public static void main(String[] args) {
        // TODO 自动生成的方法存根
        System.out.println("请输入5个数进行排序:");
        String Arrays[] = new String[5];
        for(int i = 0;i < 5;i++) {
            Scanner S = new Scanner(System.in);
            Arrays[i] = S.next();
        }
        sort(Arrays);
        System.out.println("排序完");
        for(int i = 0;i < 5;i++) {
            System.out.println(""+Arrays[i]);
        }
    }
}

 

赞(5) 打赏
有问题的朋友随时留言,或者加我为好友。我的QQ是805375353. <<苏木三少博客 » <每天一个> 算法实现之快速排序

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

十年之约