快速排序及其四种优化版本
基础代码
int pivitition(int arr[], int low, int high);
void swap(int* a, int* b)
{
int pivotkey = *a;
*a = *b;
*b = pivotkey;
}
void qsort(int arr[], int low,int high)
{
int pivot;
if (low<high)
{
pivot = pivitition(arr, low, high);
qsort(arr, low, pivot - 1);
qsort(arr, pivot + 1, high);
}
}
int pivitition(int arr[], int low, int high)
{
int pivotkey;
pivotkey = arr[low];
while (low < high)
{
while (low<high && arr[high]>=pivotkey)
{
high--;
}
swap(&arr[high], &arr[low]);
while (low < high && arr[low] <=pivotkey)
{
low++;
}
swap(&arr[low], &arr[high]);
}
return low;
}
int main()
{
int arr[9] = { 6,1,0,12,7,5,4,3,23 };
qsort(arr, 0, 8);
for (int i = 0; i < 9; i++)
{
printf(" %d", arr[i]);
}
}
优化:三数取中
int pivitition(int arr[], int low, int high);
void swap(int* a, int* b)
{
int pivotkey = *a;
*a = *b;
*b = pivotkey;
}
void qsort(int arr[], int low, int high)
{
int pivot;
if (low < high)
{
pivot = pivitition(arr, low, high);
qsort(arr, low, pivot - 1);
qsort(arr, pivot + 1, high);
}
}
int pivitition(int arr[], int low, int high)
{
int pivotkey;
int m = low + (high - low) / 2;
if (arr[low] > arr[high])
swap(&arr[low], &arr[m]);
if (arr[m] > arr[high])
swap(&arr[m], &arr[high]);
if (arr[m] > arr[low])
swap(&arr[m], &arr[low]);
pivotkey = arr[low];
while (low < high)
{
while (low < high && arr[high] >= pivotkey)
{
high--;
}
swap(&arr[high], &arr[low]);
while (low < high && arr[low] <= pivotkey)
{
low++;
}
swap(&arr[low], &arr[high]);
}
return low;
}
int main()
{
int arr[9] = { 6,1,0,12,7,5,4,3,23 };
qsort(arr, 0, 8);
for (int i = 0; i < 9; i++)
{
printf(" %d", arr[i]);
}
}
优化2:采用替换而非交换
int pivitition(int arr[], int low, int high);
void swap(int* a, int* b)
{
int pivotkey = *a;
*a = *b;
*b = pivotkey;
}
void qsort(int arr[], int low, int high)
{
int pivot;
if (low < high)
{
pivot = pivitition(arr, low, high);
qsort(arr, low, pivot - 1);
qsort(arr, pivot + 1, high);
}
}
int pivitition(int arr[], int low, int high)
{
int pivotkey;
pivotkey = arr[low];
int temp = pivotkey;/*++++++++++++++++不会*/
while (low < high)
{
while (low < high && arr[high] >= pivotkey)
{
high--;
}
arr[low] = arr[high];/*++++++++++++++++不会*/
while (low < high && arr[low] <= pivotkey)
{
low++;
}
arr[high] = arr[low];/*++++++++++++++++不会*/
}
arr[low] = temp;
return low;
}
int main()
{
int arr[14] = { 6,1,56,23,2,8,32,0,12,7,5,4,3,23 };
qsort(arr, 0, 13);
for (int i = 0; i < 14; i++)
{
printf(" %d", arr[i]);
}
}
优化3:若数组长度太少则直接使用直接插入排序
void swap(int* a, int* b)
{
int pivotkey = *a;
*a = *b;
*b = pivotkey;
}
void insertion(int arr[], int length)
{
int i, j;
for (i = 1; i < length; i++)
{
if (arr[i] < arr[i - 1])
{
int temp = arr[i];
for (j = i - 1; arr[j]>temp; j --)
{
arr[j + 1] = arr[j];
}
arr[j+1] = temp;
}
}
}
int pivitition(int arr[], int low, int high)
{
int pivotkey;
pivotkey = arr[low];
while (low < high)
{
while (low < high && arr[high] >= pivotkey)
{
high--;
}
swap(&arr[high], &arr[low]);
while (low < high && arr[low] <= pivotkey)
{
low++;
}
swap(&arr[low], &arr[high]);
}
return low;
}
void qsort(int arr[], int low, int high)
{
int pivot;
if (( high - low )>MAX_LENGTH)
{
pivot = pivitition(arr, low, high);
qsort(arr, low, pivot - 1);
qsort(arr, pivot + 1, high);
}
else
{
insertion(arr, 9);
}
}
int main()
{
int arr[9] = { 6,1,0,12,7,5,4,3,23 };
qsort(arr, 0, 8);
for (int i = 0; i < 9; i++)
{
printf(" %d", arr[i]);
}
}
优化4:采用迭代而非递归
void swap(int* a, int* b)
{
int pivotkey = *a;
*a = *b;
*b = pivotkey;
}
void insertion(int arr[], int length)
{
int i, j;
for (i = 1; i < length; i++)
{
if (arr[i] < arr[i - 1])
{
int temp = arr[i];
for (j = i - 1; arr[j] > temp; j--)
{
arr[j + 1] = arr[j];
}
arr[j + 1] = temp;
}
}
}
int pivitition(int arr[], int low, int high)
{
int pivotkey;
pivotkey = arr[low];
while (low < high)
{
while (low < high && arr[high] >= pivotkey)
{
high--;
}
swap(&arr[high], &arr[low]);
while (low < high && arr[low] <= pivotkey)
{
low++;
}
swap(&arr[low], &arr[high]);
}
return low;
}
void qsort(int arr[], int low, int high)
{
int pivot;
if ((high - low) > MAX_LENGTH)
{
while (low < high)
{
pivot = pivitition(arr, low, high);
qsort(arr, low, pivot - 1);
low = pivot + 1;
}
}
else
{
insertion(arr, 9);
}
}
int main()
{
int arr[9] = { 6,1,0,12,7,5,4,3,23 };
qsort(arr, 0, 8);
for (int i = 0; i < 9; i++)
{
printf(" %d", arr[i]);
}
}