排序算法C語言版快速排序

1、快速排序算法思想簡單描述：快速排序是對冒泡排序的一種本質(zhì)改進(jìn)。它的基本思想是通過一趟掃描后，使得排序序列的長度能大幅度地減少。在冒泡排序中，一次掃描只能確保最大數(shù)值的數(shù)移到正確位置，而待排序序列的長度可能只減少1?？焖倥判蛲ㄟ^一趟掃描，就能確保某個(gè)數(shù)（以它為基準(zhǔn)點(diǎn)吧）的左邊各數(shù)都比它小，右邊各數(shù)都比它大。然后又用同樣的方法處理它左右兩邊的數(shù)，直到基準(zhǔn)點(diǎn)的左右只有一個(gè)元素為止。它是由于1962年提出的。顯然快速排序可以用遞歸實(shí)現(xiàn)，當(dāng)然也可以用?；膺f歸實(shí)現(xiàn)。下面的函數(shù)是用遞歸實(shí)現(xiàn)的，有興趣的朋友可以改成非遞歸的?？焖倥判蚴遣环€(wěn)定的。最理想情況算法時(shí)間復(fù)雜度O(nlog2n)，最壞O(n2)算法實(shí)

2、現(xiàn)：/*功能：快速排序輸入：數(shù)組名稱（也就是數(shù)組首地址）、數(shù)組中元素個(gè)數(shù)*/void quick_sort(int *x, int low, int high)int i, j, t;if (low < high) /*要排序的元素起止下標(biāo)，保證小的放在左邊，大的放在右邊。這里以下標(biāo)為low的元素為基準(zhǔn)點(diǎn)*/ i = low; j = high; t = *(x+low); /*暫存基準(zhǔn)點(diǎn)的數(shù)*/ while (i<j) /*循環(huán)掃描*/ while (i<j && *(x+j)>t) /*在右邊的只要比基準(zhǔn)點(diǎn)大仍放在右邊*/ j-; /*前移一個(gè)位置*

3、/ if (i<j) *(x+i) = *(x+j); /*上面的循環(huán)退出：即出現(xiàn)比基準(zhǔn)點(diǎn)小的數(shù)，替換基準(zhǔn)點(diǎn)的數(shù)*/ i+; /*后移一個(gè)位置，并以此為基準(zhǔn)點(diǎn)*/ while (i<j && *(x+i)<=t) /*在左邊的只要小于等于基準(zhǔn)點(diǎn)仍放在左邊*/ i+; /*后移一個(gè)位置*/ if (i<j) *(x+j) = *(x+i); /*上面的循環(huán)退出：即出現(xiàn)比基準(zhǔn)點(diǎn)大的數(shù)，放到右邊*/ j-; /*前移一個(gè)位置*/ *(x+i) = t; /*一遍掃描完后，放到適當(dāng)位置*/ quick_sort(x,low,i-1); /*對基準(zhǔn)點(diǎn)左邊的數(shù)再執(zhí)行快速排