目錄
1.快排思路
2.分塊實作
3.代碼實作
1.快排思路
快速排序的基本思路就是選擇一個基數.（我們這個基數的選擇都是每一組最左邊的數）
然后排成：
1.基數左邊都是不大于它的，左邊都是不小于它的
2.然后左邊、右邊繼續進行這個基本思路
以完成排序作為最后的結束
2.分塊實作
以6個數為一個例子吧！
4，2 ，6，3，1，5
第一步：確定一個基數，以每次排序最左邊的數為基數，本次是4，
第二步：左邊（用i表示）從第二個數開始與基數進行比較（遇見比基數大的停止比較），右邊（用j表示）從最右邊開始與基數進行比較（遇見比基數小的停止比較）
第三步：當i，j停止時，它們所對應的值進行交換，直到i，j同時指向同一個值的時候，將這個值與基數進行交換，
接著進行回圈這三個步驟，每一次基數的左邊進行上面的操作，每一次基數的右邊也進行上面的操作，直至排序完成，
3.代碼實作
1.創建一個較大一點的陣列（用于儲存輸入的數）和需要排序的個數
這里先創建全域變數，為了減少記憶體的利用
#include <stdio.h>
int arr[100], n;
int main()
{
return 0;
}2.輸入需要排序的個數和輸入一組數
int a;
scanf("%d", &n);
for (a = 0; a < n; a++)
{
scanf("%d", &arr[a]);
}3.排序（核心）（創建函式進行排序）
1）以最左邊的值為基數，從最右邊的數進行比較，遇到小于或者等于基數的值的時候停止，記下此時該數的下標，然后左邊開始查找，遇到大于或者等于基數的值的時候停止，記下此時該數的下標，
while (arr[j] >= arr[temp]&&i<j)
{
j--;
}
while (arr[i] <= arr[temp] && i < j)
{
i++;
}2）交換下標所對應的數，當左右下標對應同一個值時，將該值與基數交換（第一次排序完畢）
while (i < j)
{
while (arr[j] >= arr[temp]&&i<j)
{
j--;
}
while (arr[i] <= arr[temp] && i < j)
{
i++;
}
t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
t = arr[left];
arr[left] = arr[i];
arr[i] = t;3）用遞回的方式不斷的進行排序，基數左邊，右邊都需要用遞回，遞回結束的條件（左下標大于右下標）
if (i > j)
return 0;
quicksort(left, i);//左
quicksort(j+1, right);//右該排序函式模塊
int quicksort(int left,int right)
{
int temp = left;
int i = left;
int j = right - 1;
int t = 0;
if (i > j)
return 0;
while (i < j)
{
while (arr[j] >= arr[temp]&&i<j)
{
j--;
}
while (arr[i] <= arr[temp] && i < j)
{
i++;
}
t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
t = arr[left];
arr[left] = arr[i];
arr[i] = t;
quicksort(left, i);//左
quicksort(j+1, right);//右
return 0;
}4）列印出來拍好的序列
for (a = 0; a < n; a++)
{
printf("%d ", arr[a]);
}
printf("\n");聽我講了這么久，我們已經實作了快速排序
下面看完整的代碼
#include <stdio.h>
int arr[100], n;
int quicksort(int left,int right)
{
int temp = left;
int i = left;
int j = right - 1;
int t = 0;
if (i > j)
return 0;
while (i < j)
{
while (arr[j] >= arr[temp]&&i<j)
{
j--;
}
while (arr[i] <= arr[temp] && i < j)
{
i++;
}
t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
t = arr[left];
arr[left] = arr[i];
arr[i] = t;
quicksort(left, i);//左
quicksort(j+1, right);//右
return 0;
}
int main()
{
int left, right;
int a;
scanf("%d", &n);
for (a = 0; a < n; a++)
{
scanf("%d", &arr[a]);
}
left = 0;
right = n;
quicksort(left,right);
for (a = 0; a < n; a++)
{
printf("%d ", arr[a]);
}
printf("\n");
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/401641.html
標籤：其他
下一篇：在C 上使用套接字的http請求