本文主要是介绍一日一码04——快速排序,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
写快速排序碰到很多问题,先列出代码,以后慢慢分析并补充。
//快速 2013/09/09#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <malloc.h>void swap(int *a, int *b){//C89不支持引用,所以C程序不要写成void swap(int &a, int &b),C++可以int tmp = *a;*a = *b;*b = tmp;
}//想了半天写出来的还跑不对,最后参考了编程珠玑的范例程序
void quickSort1(int* a, int l, int r){int i,m = l;if (l >= r){return;}for (i = l+1; i <= r; ++i){ //误写成过i<rif (a[i] < a[l]){swap(&a[++m],&a[i]);} }swap(&a[l],&a[m]);quickSort1(a, l, m-1);quickSort1(a, m+1, r);
}void initArr(int* a, int n){int i;srand(time(NULL));for(i = 0; i < n; i++){a[i] = rand()%100;}
}void printArr(int* a, int n){int i;for (i = 0;i < n; i++){printf("%d,",a[i]);}printf("\n");
}void main(){int* arr;int n;printf("Input the size of array:");scanf("%d",&n);arr = (int *)malloc(n*sizeof(int));initArr(arr,n);printArr(arr,n);quickSort1(arr,0,n-1);printArr(arr,n);}
/**
int partiton3(int data[], int low, int high) //low <= high
{ const int pivot = data[low]; while (pivot < data[high]) --high; const int end = high; //记录pivot将被交换到哪个位置 while (low < high) { int tmp = data[high]; data[high] = data[low]; data[low] = tmp; while (data[++low] < pivot) {} while (pivot < data[--high]) {} } //再进行一次交换,保证data[low]等于pivot data[end] = data[low]; data[low] = pivot; return low;
} void Quicksort(int *A,int first,int last)
{ int i=first+1; int j=last; int temp; if(first<last) { int p=A[first]; do{ while(A[i]<=p&&i<last) { i++; } while(A[j]>=p&&j>first) //更加注重j的扫描比较范围(last~first+1),i的扫描比较范围(first+1~last-1),因为A[j]会与A[first]交换 { j--; } if(i<=j) SWAP(A[i],A[j],temp); }while(i<j); SWAP(A[j],A[first],temp); //注意这里的A[first]千万不能换成p,否则只改变了A[j]的值而没改变A[first]的值 Quicksort(A,first,j-1); //当i=j时指向的元素的值一定等于A[first],而其又与A[first]交换,所以快速排序不稳定 Quicksort(A,j+1,last); }
}
**/
这篇关于一日一码04——快速排序的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!