求快速排序算法
急求快速排序算法，最好有实现
[解决办法]
void QuikSort(int a[], long low, long high)
{
if(low >= high)
{
return;
}
long nlow = low;
long nhigh = high;
int temp = 0;
bool flag = false;
while(nlow<nhigh)
{
if(a[nlow] > a[nhigh])
{
temp = a[nlow];
a[nlow] = a[nhigh];
a[nhigh] = temp;
flag = !flag;
}
if(flag)
{
nlow++;
}
else
{
nhigh--;
}
}
QuikSort(a, low, nhigh);
QuikSort(a, nhigh+1, high);
}
[解决办法]
#include "stdio.h"
void swap(int *a,int *b)
{ /*序列中元素位置的交换*/
int tmp;
tmp = *a;
*a = *b;
*b = tmp;
}
void print(int k[])
{
int i;
static int cont = 0;
cont++;
printtf("\n第 %d 次: ",cont);
for(i=0;i<10;i++)
{
printtf("%d ",k[i]);
}
printf("\n");
}
void quicksort(int k[], int s,int t)
{ /*快速排序*/
int i,j;
if(s<t)//划分结束条件
{
i = s;
j = t+1;
while(1)
{
do
{
i++;
}while( !(k[s]<=k[i]
[解决办法]
i==t) ); //从第一个开始求出第一个大于基准值的元素位置i
do
{
j--;
}while(!(k[s]>=k[j]
[解决办法]
j==s)); //从最后开始求出第一个小于基准值的元素位置j
if(i<j)
{
swap(&k[i],&k[j]); /*交换k[i]和k[j]的位置*/
//print(k);
}
else
break;
}
swap(&k[s],&k[j]); //将基准元素与从后往前的第一个大于s的元素进行交换，即放在中间
quicksort(k,s,j-1); /*递归排序基准元素前面的子序列*/
quicksort(k,j+1,t); /*递归排序基准元素后面的子序列*/
}
}
int main()
{
int k[10]={2,5,6,3,7,8,0,9,12,1} , i;
printf("The data array is\n") ;
for(i=0;i<10;i++) /*显示原序列之中的元素*/
printf("%d ",k[i]);
printf("\n");
quicksort(k,0,9); /*快速排序*/
printf("\nThe result of quick sorting for the array is\n");
for(i=0;i<10;i++) /*显示排序后的结果*/
printf("%d ",k[i]);
printf("\n");
return 0;
}
[解决办法]
#include <stdio.h>
#include <stdlib.h>
#define NUM_OF_ARRAY100
void quick_sort(int *array, int left, int right)
{
int old_left = left;
int old_right = right;
int standard_data = array[left];
printf(".");
while(left < right)
{
while((array[right] >= standard_data) && (left < right))right--;
if(left != right)
{
array[left] = array[right];
left++;
}
while((array[left] <= standard_data) && (left < right))left++;
if(left != right)
{
array[right] = array[left];
right--;
}
}
array[left] = standard_data;
if(old_left < left)
quick_sort(array, old_left, left-1);
if(old_right > left)
quick_sort(array, left+1, old_right);
}
int main(int argc, char *argv[])
{
int arr[NUM_OF_ARRAY] = {0};
int i=0;
srand(getpid());
for(i=0; i<NUM_OF_ARRAY; i++)
{
arr[i] = rand();
printf("%d\n", arr[i]);
}
quick_sort(arr, 0, NUM_OF_ARRAY-1);
printf("\n");
for(i=0; i<NUM_OF_ARRAY; i++)
{
printf("%d\n", arr[i]);
}
return 0;
}
[解决办法]
int Partition(int nArray[], int nLeft, int nRight)
{
int nMiddle = (nLeft + nRight) / 2;
int nIndex = nLeft - 1;
for(int i = nLeft; i <= nRight; i++)
{
if(nMiddle == i)
continue;
if(nArray[i] <= nArray[nMiddle])
{
nIndex++;
if(nIndex == nMiddle)
nIndex++;
Swap(nArray, i, nIndex);
}
}
if(nIndex < nMiddle)
nIndex++;
Swap(nArray, nIndex, nMiddle);
return nIndex;
}
void Sort_Fast(int nArray[], int nLeft, int nRight)
{
if(nLeft >= nRight)
return;
int nMiddle = Partition(nArray, nLeft, nRight);
Sort_Fast(nArray, nLeft,nMiddle - 1);
Sort_Fast(nArray, nMiddle + 1, nRight);
}
直接取的中值作为阈值。
[解决办法]
仅供参考：
/*********************************************************
* From C PROGRAMMING: A MODERN APPROACH, Second Edition *
* By K. N. King *
* Copyright (c) 2008, 1996 W. W. Norton & Company, Inc. *
* All rights reserved. *
* This program may be freely distributed for class use, *
* provided that this copyright notice is retained. *
*********************************************************/
/* qsort.c (Chapter 9, page 207) */
/* Sorts an array of integers using Quicksort algorithm */
#include <stdio.h>
#define N 10
void quicksort(int a[], int low, int high);
int split(int a[], int low, int high);
int main(void)
{
int a[N], i;
printf("Enter %d numbers to be sorted: ", N);
for (i = 0; i < N; i++)
scanf("%d", &a[i]);
quicksort(a, 0, N - 1);
printf("In sorted order: ");
for (i = 0; i < N; i++)
printf("%d ", a[i]);
printf("\n");
return 0;
}
void quicksort(int a[], int low, int high)
{
int middle;
if (low >= high) return;
middle = split(a, low, high);
quicksort(a, low, middle - 1);
quicksort(a, middle + 1, high);
}
int split(int a[], int low, int high)
{
int part_element = a[low];
for (;;) {
while (low < high && part_element <= a[high])
high--;
if (low >= high) break;
a[low++] = a[high];
while (low < high && a[low] <= part_element)
low++;
if (low >= high) break;
a[high--] = a[low];
}
a[high] = part_element;
return high;
}