|
#include <stdio.h>
#include <windows.h>
void QuickSort(int *arr, int left, int right);
int Partition(int *arr, int left, int right);
int main(void)
{
?? ?int arr[] = {5, 1, 9, 3, 7, 4, 8, 6, 2};
?? ?int n = sizeof(arr)/sizeof(int);
?? ?QuickSort(arr, 0, n-1);
?? ?for(int i = 0; i < n; i++)
?? ?{
?? ??? ?printf("%d ", arr[i]);
?? ?}
?? ?printf("\n");
?? ?system("pause");
?? ?return 0;
}
void QuickSort(int *arr, int left, int right)
{?? ?
?? ?if(left < right)
?? ?{
?? ??? ?int pivot = Partition(arr, left, right);
?? ??? ?QuickSort(arr, left, pivot-1);
?? ??? ?QuickSort(arr, pivot+1, right);
?? ?}
}
int Partition(int *arr, int left, int right)
{?? ?
?? ?int temp = arr[left];
?? ?while(left < right)
?? ?{
?? ??? ?while(left < right && arr[right] >= temp)
?? ??? ?{
?? ??? ??? ?right--;
?? ??? ?}
?? ??? ?arr[left] = arr[right];
?? ??? ?while(left < right && arr[left] <= temp)
?? ??? ?{
?? ??? ??? ?left++;
?? ??? ?}
?? ??? ?arr[right] = arr[left];
?? ?}
?? ?arr[left] = temp;
?? ?return left;
}
?
|