快速排序實例程序(C語言)
快速排序實例程序,C語言實現的詳細如下:
#include <stdio.h>
#include <stdbool.h>
#define MAX 7
int intArray[MAX] = {4,6,3,2,1,9,7};
void printline(int count){
int i;
for(i = 0;i <count-1;i++){
printf("=");
}
printf("=\n");
}
void display(){
int i;
printf("[");
// navigate through all items
for(i = 0;i<MAX;i++){
printf("%d ",intArray[i]);
}
printf("]\n");
}
void swap(int num1, int num2){
int temp = intArray[num1];
intArray[num1] = intArray[num2];
intArray[num2] = temp;
}
int partition(int left, int right, int pivot){
int leftTutorialser = left -1;
int rightTutorialser = right;
while(true){
while(intArray[++leftTutorialser] < pivot){
//do nothing
}
while(rightTutorialser > 0 && intArray[--rightTutorialser] > pivot){
//do nothing
}
if(leftTutorialser >= rightTutorialser){
break;
}else{
printf(" item swapped :%d,%d\\n",
intArray\[leftTutorialser\],intArray\[rightTutorialser\]);
swap(leftTutorialser,rightTutorialser);
}
}
printf(" pivot swapped :%d,%d\n", intArray[leftTutorialser],intArray[right]);
swap(leftTutorialser,right);
printf("Updated Array: ");
display();
return leftTutorialser;
}
void quickSort(int left, int right){
if(right-left <= 0){
return;
}else{
int pivot = intArray[right];
int partitionTutorials = partition(left, right, pivot);
quickSort(left,partitionTutorials-1);
quickSort(partitionTutorials+1,right);
}
}
main(){
printf("Input Array: ");
display();
printline(50);
quickSort(0,MAX-1);
printf("Output Array: ");
display();
printline(50);
}
如果我們編譯並運行上述程序,那麼這將產生以下結果 -
Input Array: [4 6 3 2 1 9 7 ]
pivot swapped :9,7
Updated Array: [4 6 3 2 1 7 9 ]
pivot swapped :4,1
Updated Array: [1 6 3 2 4 7 9 ]
item swapped :6,2
pivot swapped :6,4
Updated Array: [1 2 3 4 6 7 9 ]
pivot swapped :3,3
Updated Array: [1 2 3 4 6 7 9 ]
Output Array: [1 2 3 4 6 7 9 ]
==================================================