（1）問題描述

創(chuàng)新互聯(lián)公司堅持“要么做到，要么別承諾”的工作理念，服務領域包括：網(wǎng)站制作、成都網(wǎng)站設計、企業(yè)官網(wǎng)、英文網(wǎng)站、手機端網(wǎng)站、網(wǎng)站推廣等服務，滿足客戶于互聯(lián)網(wǎng)時代的鶴壁網(wǎng)站設計、移動媒體設計的需求，幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡建設合作伙伴！

對于任意的無序正整數(shù)序列，寫程序用快速排序算法將其排序成按值非遞減有序序列。

（2）輸入描述

文本文件“input.txt”中保存了n個測試用例，文件以-1結束。每個用例的第一行m表示第一個待排序整數(shù)序列的元素個數(shù)，第二行為該序列的m個元素。

（3）輸出描述

輸出結果保存在文本文件“output.txt”中。對于每個測試用例均有二行輸出，第一行輸出“Case #:##”，#表示用例的編號（1…n），##表示排序后有序序列的元素個數(shù)，第二輸出##個按值非遞減有序元素。

（4）輸入示例

?5

10? 1? 8? 4?? 30

7

35? 60? 50? 2?? 20?? 4?? 86

3

38? 100? 45

-1

（5）輸出示例???

?Case 1:5

4? 8? 10? 30

Case 2:7

2?? 4? 20? 35? 50? 60? 86

Case 3:3

38? 45? 100

代碼實現(xiàn)：

#define _CRT_SECURE_NO_WARNINGS
#include#includevoid swap(int a[], int low, int high) //交換兩個數(shù)的值
{
    int t = a[low];
    a[low] = a[high];
    a[high] = t;
}

int getpoint(int a[], int low, int high)  //計算基準點，分割為左右兩個數(shù)組
{
    int point = a[low];//基準點等于第一個元素
    while (low< high)
    {
        while (low< high && a[high] >= point)//控制high指針比較并左移
        {
            high--;
        }
        swap(a, low, high);
        while (low< high && a[low]<= point)//控制low指針比較并右移
        {
            low++;
        }
        swap(a, low, high);
    }
    return low;//返回基準點位置
}
    
    

void quicksort(int a[], int low, int high)  //low:起始位置 high:末尾位置
{
    if (low< high) {
        int point = getpoint(a, low, high);//計算基準點
        quicksort(a, low, point - 1);  //對基準點的左邊進行排序
        quicksort(a, point + 1, high);//對基準點的右邊進行排序
    }
}

int main()
{
    FILE* fin = fopen("D:\\input.txt", "r");
    FILE* fout = fopen("D:\\output.txt", "w");
    int N; //數(shù)組中的元素個數(shù)
    int a[5000];
    int count = 0;//記錄一共有多少組數(shù)
    int i, j;
    while (true)
    {
        fscanf(fin, "%d", &N);
        if (N == -1) break;//文件以-1結束
        count++; 
        fprintf(fout, "case %d:%d\n", count, N);
        for (i = 0; i< N; i++)
        {
            fscanf(fin, "%d", &a[i]);
        }
        quicksort(a, 0, N - 1);
        for (j = 0; j< N; j++)
        {
            fprintf(fout, "%d ", a[j]);
        }
        fprintf(fout, "\n");
    }
    fclose(fin);
    fclose(fout);
    system("pause");
}

運行結果：（當然，題目真正的input.txt是一個巨長無比的文件，為了方便展示我用題干的樣例寫數(shù)據(jù)進行測試啦）

算法時間復雜度分析：

最壞情況：每一輪都分不成兩組，一共要分n輪

時間復雜度:O(n^2）

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

當前文章：快速排序算法C語言實現(xiàn)-創(chuàng)新互聯(lián)
轉載來于：http://jinyejixie.com/article16/cshggg.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供關鍵詞優(yōu)化、外貿(mào)建站、網(wǎng)站排名、外貿(mào)網(wǎng)站建設、網(wǎng)站營銷、域名注冊

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉載內(nèi)容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯(lián)