1039: 快速排序（1）

题目描述

已知快速排序的部分代码如下，勿改动，请补充实现快速排序函数：void QuickSort(int first,int end); //quickSort 要求：输出每趟排序结果
#include
using namespace std;
const int MaxSize=100;
class List
{
private:
int r[MaxSize+1];
int n;
public:
List(){n=0;} //empty list
void InsertR(int k) //表尾插入
{ r[++n]=k;}
void Display(); //display
void QuickSort(int first,int end); //quickSort
void QuickSort()
{
QuickSort(1,n);
}
};

void List::Display()
{
for(int i=1;i<=n;i++)
cout<cout<<”\n”;
}
int main()
{
List L;
while(1)
{
int k;
cin>>k;
if(!k) break;
L.InsertR(k);
}
//L.Display();
L.QuickSort();
//L.Display();
return 0;
}

输入

输出

样例输入

12 21 32 2 4 24 21 432 23 9 0

样例输出

9 4 2 12 32 24 21 432 23 21
2 4 9 12 32 24 21 432 23 21
2 4 9 12 32 24 21 432 23 21
2 4 9 12 21 24 21 23 32 432
2 4 9 12 21 24 21 23 32 432
2 4 9 12 21 23 21 24 32 432
2 4 9 12 21 21 23 24 32 432

提示

来源

提交

import java.util.Scanner;
class Ilist{
    int[] r;
    int n;
    int MaxSize = 100;
    public Ilist() {
        n = 0;
        r = new int[MaxSize];
    }
    void InsertR(int k){
        r[++n] = k;
    }
    void Display(){
//        System.out.print("Data:");
        for (int i = 1; i <= n; i++) {
            System.out.print(r[i]+" ");
        }
        System.out.println();
    }
    void QuickSort(){
        QuickSort(1,n);
    }
    void QuickSort(int first,int end){
        if (first < end) {
            int pivot = Partition(r, first, end);
            Display();
            QuickSort(first, pivot - 1);
            QuickSort(pivot + 1, end);
        }
    }
    int Partition(int r[], int first, int end) {
        int i = first, j = end;
        while (i < j) {
            while (i < j && r[i] <= r[j])j--;
            if (i < j) {
                int temp = r[j];
                r[j] = r[i];
                r[i] = temp;
                i++;
            }
            while (i < j && r[i] <= r[j])i++;
            if (i < j) {
                int temp = r[j];
                r[j] = r[i];
                r[i] = temp;
                j--;
            }
        }
        return i;
    }
}
public class Main {
    public static void main(String[] args) {
        Ilist ilist = new Ilist();
        Scanner scanner = new Scanner(System.in);
        int key;
        while(true){
            int x = scanner.nextInt();
            if(x == 0)break;
            ilist.InsertR(x);
        }
        ilist.QuickSort();
    }
}