常用排序算法之快速排序

缺乏、安全感 2022-08-22 00:07 167阅读 0赞

## 一、算法简介 ##

快速排序的基本步骤是：

1.  每一次排序时选择一个关键字，一趟排序后待排序的数据被分割成两部分，其中一部分的数据均比该关键字大，另一部分的关键字均比该关键字小；
2.  分别对两部分的数据继续进行排序（可递归进行）。

## 二、算法解析 ##

数据: 21, 30, 49, 23, 30, 21, 16, 9  
一次排序过程为：

1.  选择第一个数 21 为关键字，并保存为 tmp，定义两个指针 i 和 j；
2.  从右往左遍历，如果比 tmp 小则替换 data\[i\] 的值，并且将 i 的指针往后移一位： data\[i ++\] = data\[j\] ；
3.  从左往右遍历，如果比 tmp 大则替换 data\[j\] 的值，并且将 j 的指针往前移一位；
4.  继续循环，如果 i == j，则替换 data\[i\] 的值： data\[i\] = tmp;
5.  分别递归 (left, i) 和 (i + 1, right) 两部分的数据。

注：一趟排序之后为：9, 16, 21, 23, 30, 21, 49, 30

## 三、代码实现 ##

数据包装类 DataWrap：

package utils;
    
    /** * 数据包装类 * @author Administrator * */
    public class DataWrap implements Comparable<DataWrap> { 
        public int data ;
        String flag ;
        public DataWrap(int data, String flag){
            this.data = data ;
            this.flag = flag ;
        }
    
        public String toString() {
            return data + flag ;
        }
    
        public int compareTo(DataWrap o) {
            return this.data > o.data ? 1 : (this.data == o.data ? 0 : -1) ;
        }
    
    }

快速排序实现类 QuickSort：

package com.wlm.sort;
    
    public class QuickSort {
    
        public static void quickSort(DataWrap[] data, int l, int r){ if(l >= r){ return ; }
            int i = l, j = r ;
            DataWrap tmp = data[i] ;
            while(i < j){
                while(i < j && data[j].compareTo(tmp) >= 0) { j -- ; }
                if(i < j) {
                    data[i ++] = data[j] ;
                }
                while(i < j && data[i].compareTo(tmp) < 0) { i ++ ; }
                if(i < j) {
                    data[j --] = data[i] ;
                }
            }
            data[i] = tmp ;
            quickSort(data, l, i) ;
            quickSort(data, i+1, r) ;
        }
    
        public static void main(String[] args) {
            DataWrap[] data = { new DataWrap(21, "") , new DataWrap(30, "") , new DataWrap(49, "") , new DataWrap(23, "") , new DataWrap(30, "*") , new DataWrap(21, "*") , new DataWrap(16, "") , new DataWrap(9, "") , } ;
            System.out.println("排序之前：\n"+java.util.Arrays.toString(data));
            quickSort(data, 0, data.length-1) ;
            System.out.println("排序之后：\n"+java.util.Arrays.toString(data));
        }
    }

输出结果为：

![这里写图片描述][20160505173353682]

[20160505173353682]: /images/20220724/bd06fd58acba438285485fe053bfe313.png