快速排序~~洛谷P1177

題目描述

利用快速排序算法将讀入的N個數從小到大排序後輸出。

快速排序是資訊學競賽的必備算法之一。對于快速排序不是很了解的同學可以自行上網查詢相關資料，掌握後獨立完成。（C++選手請不要試圖使用STL，雖然你可以使用sort一遍過，但是你并沒有掌握快速排序算法的精髓。）

輸入輸出格式

輸入格式： 

輸入檔案sort.in的第1行為一個正整數N，第2行包含N個空格隔開的正整數a[i]，為你需要進行排序的數，資料保證了A[i]不超過1000000000。

輸出格式： 

輸出檔案sort.out将給定的N個數從小到大輸出，數之間空格隔開，行末換行且無空格。

輸入輸出樣例

輸入樣例#1： 

5 

4 2 4 5 1 

輸出樣例#1： 

1 2 4 4 5

說明

對于20%的資料，有N≤1000；

對于100%的資料，有N≤100000。

題解：就是簡單得快速排序模闆

第一個是簡單得挖坑填數法：

#include<iostream>
#include<cstring>
using namespace std;
void quicksort(int a[],int ac,int ak)
{
    if(ac>=ak)return ;
    swap(a[ac],a[(ac+ak)/2]);
    int head=ac,tail=ak,x=a[ac];
    while(head<tail)
    {
        while(head<tail&&a[tail]>x)tail--;
        if(head<tail)a[head++]=a[tail];
        while(head<tail&&a[head]<x)head++;
        if(head<tail)a[tail--]=a[head];
    }
    a[head]=x;
    quicksort(a,ac,head-1);
    quicksort(a,head+1,ak);
}
int main()
{
    int n,a[100005];
    memset(a,0,sizeof(a));
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    quicksort(a,0,n-1);
    for(int i=0;i<n-1;i++)cout<<a[i]<<' ';
    cout<<a[n-1];
    return 0;
}
           

第二種就是很慢得交換資料，這種方法被tle了，我也很無奈：

#include <stdio.h> 
#include <cstring>
#include <iostream>
using namespace std;
void QuickSort(int array[], int low, int high)
{
    int i = low; 
    int j = high;
    if(i > j)
        return;
    int temp = array[low];
    while(i != j)
    {
        while(array[j] >= temp && i < j)
            j--;
        while(array[i] <= temp && i < j)
            i++;
        if(i < j)
            swap(array[i], array[j]);
    }
    swap(array[low], array[i]);
    QuickSort(array, low, i - 1);
    QuickSort(array, i + 1, high);
}
int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++) cin>>a[i];
    QuickSort(a, 0, n-1);

    for(int i = 0; i < n-1; i++)
    {
        printf("%d ",a[i]);
    }
    cout<<a[n-1]<<endl;
    return 0;
}