快速排序演算法c語言,快速排序演算法c語言while

本文目錄一覽：

• 1、快速排序c語言
• 2、用C語言編寫一個快速排序演算法 輸入10個數
• 3、用C語言編程實現快速排序演算法

快速排序c語言

.example-btn{color:#fff;background-color:#5cb85c;border-color:#4cae4c}.example-btn:hover{color:#fff;background-color:#47a447;border-color:#398439}.example-btn:active{background-image:none}div.example{width:98%;color:#000;background-color:#f6f4f0;background-color:#d0e69c;background-color:#dcecb5;background-color:#e5eecc;margin:0 0 5px 0;padding:5px;border:1px solid #d4d4d4;background-image:-webkit-linear-gradient(#fff,#e5eecc 100px);background-image:linear-gradient(#fff,#e5eecc 100px)}div.example_code{line-height:1.4em;width:98%;background-color:#fff;padding:5px;border:1px solid #d4d4d4;font-size:110%;font-family:Menlo,Monaco,Consolas,”Andale Mono”,”lucida console”,”Courier New”,monospace;word-break:break-all;word-wrap:break-word}div.example_result{background-color:#fff;padding:4px;border:1px solid #d4d4d4;width:98%}div.code{width:98%;border:1px solid #d4d4d4;background-color:#f6f4f0;color:#444;padding:5px;margin:0}div.code div{font-size:110%}div.code div,div.code p,div.example_code p{font-family:”courier new”}pre{margin:15px auto;font:12px/20px Menlo,Monaco,Consolas,”Andale Mono”,”lucida console”,”Courier New”,monospace;white-space:pre-wrap;word-break:break-all;word-wrap:break-word;border:1px solid #ddd;border-left-width:4px;padding:10px 15px} 排序演算法是《數據結構與演算法》中最基本的演算法之一。排序演算法可以分為內部排序和外部排序，內部排序是數據記錄在內存中進行排序，而外部排序是因排序的數據很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。常見的內部排序演算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸併排序、快速排序、堆排序、基數排序等。以下是快速排序演算法：

快速排序是由東尼·霍爾所發展的一種排序演算法。在平均狀況下，排序 n 個項目要 Ο(nlogn) 次比較。在最壞狀況下則需要 Ο(n2) 次比較，但這種狀況並不常見。事實上，快速排序通常明顯比其他 Ο(nlogn) 演算法更快，因為它的內部循環（inner loop）可以在大部分的架構上很有效率地被實現出來。

快速排序使用分治法（Divide and conquer）策略來把一個串列（list）分為兩個子串列（sub-lists）。

快速排序又是一種分而治之思想在排序演算法上的典型應用。本質上來看，快速排序應該算是在冒泡排序基礎上的遞歸分治法。

快速排序的名字起的是簡單粗暴，因為一聽到這個名字你就知道它存在的意義，就是快，而且效率高！它是處理大數據最快的排序演算法之一了。雖然 Worst Case 的時間複雜度達到了 O(n?)，但是人家就是優秀，在大多數情況下都比平均時間複雜度為 O(n logn) 的排序演算法表現要更好，可是這是為什麼呢，我也不知道。好在我的強迫症又犯了，查了 N 多資料終於在《演算法藝術與信息學競賽》上找到了滿意的答案：

快速排序的最壞運行情況是 O(n?)，比如說順序數列的快排。但它的平攤期望時間是 O(nlogn)，且 O(nlogn) 記號中隱含的常數因子很小，比複雜度穩定等於 O(nlogn) 的歸併排序要小很多。所以，對絕大多數順序性較弱的隨機數列而言，快速排序總是優於歸併排序。

1. 演算法步驟

從數列中挑出一個元素，稱為 “基準”（pivot）;

重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分區退出之後，該基準就處於數列的中間位置。這個稱為分區（partition）操作；

遞歸地（recursive）把小於基準值元素的子數列和大於基準值元素的子數列排序；

2. 動圖演示

代碼實現 JavaScript 實例 function quickSort ( arr , left , right ) {

    var len = arr. length ,

        partitionIndex ,

        left = typeof left != ‘number’ ? 0 : left ,

        right = typeof right != ‘number’ ? len – 1 : right ;

    if ( left

用C語言編寫一個快速排序演算法 輸入10個數

1、「快速排序法」使用的是遞歸原理，下面一個例子來說明「快速排序法」的原理。首先給出一個數組{53，12，98，63，18，72，80，46， 32，21}，先找到第一個數–53，把它作為中間值，也就是說，要把53放在一個位置，使得它左邊的值比它小，右邊的值比它大。{21，12，32， 46，18，53，80，72，63，98}，這樣一個數組的排序就變成了兩個小數組的排序–53左邊的數組和53右邊的數組，而這兩個數組繼續用同樣的方式繼續下去，一直到順序完全正確。一般來說，冒泡法是程序員最先接觸的排序方法，它的優點是原理簡單，編程實現容易，但它的缺點就是速度太慢。

2、快速排序代碼：

#includestdio.h

void quicksort(int a[],int left,int right)

{

    int i,j,temp;

    i=left;

    j=right;

    temp=a[left];

    if(leftright)

        return;

    while(i!=j)

    {

        while(a[j]=tempji)

            j–;

        if(ji)

            a[i++]=a[j];

        while(a[i]=tempji)

            i++;

        if(ji)

            a[j–]=a[i];

    }

    a[i]=temp;

    quicksort(a,left,i-1);

    quicksort(a,i+1,right);

}

void main()

{

    int a[]={53,12,98,63,18,72,80,46,32,21};

    int i;

    quicksort(a,0,9);

    /*排好序的結果*/

    for(i=0;i10;i++)

        printf(“%4d\n”,a[i]);

}

用C語言編程實現快速排序演算法

給個快速排序你參考參考

/********************** 快速排序 ****************************

基本思想：在待排序的n個記錄中任取一個記錄（通常取第一個記錄），

  以該記錄為基準，將當前的無序區劃分為左右兩個較小的無

  序子區，使左邊的記錄均小於基準值，右邊的記錄均大於或

  等於基準值，基準值位於兩個無序區的中間位置（即該記錄

  最終的排序位置）。之後，分別對兩個無序區進行上述的劃

  分過程，直到無序區所有記錄都排序完畢。

*************************************************************/

/*************************************************************

函數名稱：static void swap(int *a, int *b)

參    數：int *a—整型指針

  int *b—整型指針

功    能：交換兩個整數的位置

返 回 值：無

說    明：static關鍵字指明了該函數只能在本文件中使用

**************************************************************/

static void swap(int *a, int *b)

{  

    int temp = *a;

    *a = *b;

    *b = temp;

}

int quickSortNum = 0; // 快速排序演算法所需的趟數

/*************************************************************

函數名稱：static int partition(int a[], int low, int high)

參    數：int a[]—待排序的數據

  int low—無序區的下限值

  int high—無序區的上限值

功    能：完成一趟快速排序

返 回 值：基準值的最終排序位置

說    明：static關鍵字指明了該函數只能在本文件中使用

**************************************************************/

static int partition(int a[], int low, int high)

{

    int privotKey = a[low];  //基準元素

    while(low  high)

{   //從表的兩端交替地向中間掃描  

        while(low  high   a[high] = privotKey)   // 找到第一個小於privotKey的值

high–;  //從high所指位置向前搜索，至多到low+1位置  

        swap(a[low], a[high]);  // 將比基準元素小的交換到低端

        while(low  high   a[low] = privotKey)   // 找到第一個大於privotKey的值

low++;  //從low所指位置向後搜索，至多到high-1位置

        swap(a[low], a[high]);  // 將比基準元素大的交換到高端

    }

quickSortNum++;  // 快速排序趟數加1

return low;  // 返回基準值所在的位置

}  

/*************************************************************

函數名稱：void QuickSort(int a[], int low, int high)

參    數：int a[]—待排序的數據

  int low—無序區的下限值

  int high—無序區的上限值

功    能：完成快速排序演算法，並將排序完成的數據存放在數組a中

返 回 值：無

說    明：使用遞歸方式完成

**************************************************************/

void QuickSort(int a[], int low, int high)

{  

    if(low  high)

{

        int privotLoc = partition(a, low, high); // 將表一分為二  

        QuickSort(a, low, privotLoc-1);          // 遞歸對低子表遞歸排序  

        QuickSort(a, privotLoc+1, high);         // 遞歸對高子表遞歸排序  

    }

}