快速排序（Java语言实现）——从控制台输入数据，排序后输出

￡神魔★判官ぃ 2022-05-28 04:41 257阅读 0赞

# 快速排序 #

## 排序思想 ##

> 通过对数据元素集合Rn 进行一趟排序划分出独立的两个部分。其中一个部分的关键字比另一部分的关键字小。然后再分别对两个部分的关键字进行一趟排序，直到独立的元素只有一个，此时整个元素集合有序。  
> 所有比R\[low\]小的放前面，所有比R\[low\] 大的放后面，然后以R\[low\]为分界，对R\[low … high\] 划分为两个子集和，再做划分。直到low >= high 。

## 实现的代码 ##

1.  第一个文件（Main.java）

import java.util.ArrayList;
    import java.util.Scanner;
    
    
    public class Main {
    
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            System.out.println("please input the data,press \"CTRL+Z\" to end input");
            ArrayList<Integer> a = new ArrayList<Integer>();
            while(sc.hasNextInt()){
                    int temp; 
                    temp= sc.nextInt();
                    a.add(temp);
                }
            new Functions().showAll(a);
            new Functions().quickSort(a,0,a.size()-1);
            new Functions().showAll(a);
        }
    
    }

1.  第二个文件（Functions.java）

package com.dlut.quickSort;
    
    import java.util.ArrayList;
    import java.util.Iterator;
    
    public class Functions {
        void quickSort(ArrayList<Integer> a,int left,int right){
                int tleft; 
                int tright;
                int temp;
                tleft= left;
    
                tright = right;
                int key = a.get(tleft);
    
                while(tleft<tright){
                     while(tleft<tright&&a.get(tright)>key){
                         tright--;
                     }
                     a.set(tleft, a.get(tright));
                    while(tleft<tright&&a.get(tleft)<key){
                        tleft++;
                    }
                    a.set(tright,a.get(tleft));
    
                    if(tleft==tright){
                      a.set(tleft, key);
                    }
    
                    if(left<tright){
                        quickSort(a,left,tleft-1);
                    }
                    if(tleft<right){
                    quickSort(a,tright+1,right);
                    }
                }
    
    
            }
    
    
        public void showAll(ArrayList<Integer> a){
            System.out.println("please show the data");
            Iterator<Integer> it = a.iterator();
            while(it.hasNext()){
                System.out.print(it.next()+"\t");
            }
            System.out.println();
        }
    }

# 运行结果 #

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

# 和其他的排序方式比较 #

![这里写图片描述][70 1]

## 总结 ##

快速排序：不稳定  
时间复杂度：nlogn

[70]: /images/20220528/67366d4d5d3d4ed5b63ef866ff58c398.png
[70 1]: /images/20220528/0476605460ca457b98e617c908bf228f.png