学步园

// 快速排序.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
using namespace std;
 
int num=10;
 
void swap(int &a, int &b)            //交换数组元素
{
    int temp = a;
    a = b;
    b = temp;
}
 
void PrintArray(int *arr)            //输出数组
{
    for(int i=0; i<num; ++i)
        cout << arr[i] << " ";
    cout << endl;
}
 
int Partition2(int *arr, int beg, int end)     //划分数组
{
    int sentinel = arr[end];               ////用区间的最后数个记录作为基准
    int i = beg-1;
    for(int j=beg; j<=end-1; j++)   //从左向右扫描，查找第1个关键字小于sentinel的记录arr[j]
    {
        if(arr[j] <= sentinel)
        {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i+1], arr[end]);
    cout << "排序过程:";
    PrintArray(arr);
    return i+1;
}
 
void QuickSort(int *arr, int beg, int end)            //实现快速排序
{
    if(beg < end)
    {
        int pivot = Partition2(arr, beg, end);
        QuickSort(arr, beg, pivot-1);
        QuickSort(arr, pivot+1, end);
    }
}
 
int main()
{
   int arr[]={2,6,7,5,8,1,9,10,3,4};
    QuickSort(arr, 0, 9);
    cout << "最后结果:";
    PrintArray(arr);
   
	char x;
	cin >> x;
	 return 0;
}