复习了一下快速排序的算法，改变了书本上的部分逻辑，顺便加上了注释以备忘
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 |
#include <stdio.h> static inline void swap ( int *a, int *b ) { int p; p = *a; *a = *b; *b = p; } static inline int selectPivot ( int num[], int left, int right ) { int middle = ( left + right ) / 2; if ( num[left] > num[right] ) swap ( &num[left], &num[right] ); if ( num[middle] > num[right]) swap ( &num[middle], &num[right] ); if ( num[left] > num[middle] ) swap ( &num[middle], &num[left] ); /* 交换枢纽值和右数倒数第二个元素的位置,用于防止i越界. * 最左元素元素比枢纽值小,防止j越界*/ swap ( &num[middle], &num[right-1] ); /* 返回枢纽值*/ return num[right-1]; } void qsortInstance(int num[], int left, int right) { /* 返回条件，当数量不足3个另做考虑，否则按3个取中值的方法 * 大概率会发生错误(因为数量只有两个，逻辑都不满足了)， * 虽然有时候又可以(发生在恰好分割出的是3个元素)*/ if ( left + 2 > right) { /* 只有一个元素,num[left]=num[right],因为是同一个数，肯定不满足这个条件，当有两个 * 元素的时候，如果前者大，则交换过来，然后停止递归*/ if ( num[left] > num[right]) swap ( &num[left], &num[right] ); return; } int pivot = selectPivot ( num, left, right ); int i = left; /* --j后导致从右边倒数第三个开始，因最右为大于枢纽值的元素，倒二为枢纽值 * 不必再比较*/ int j = right-1; while ( 1 ) { while ( num[++i] < pivot ); while ( num[--j] > pivot ); /* 假设到这个判断语句，i，j相邻，经过交换再回到while循环 * i再往右就是从j交换过来的比不比pivot小的值，i肯定会停下, * j同理, 都走了一个单位，假设i，j间隔1，互换之后返回while循环比较 * ,中间i，j可能重叠，因此值刚可能好是枢纽值，二者都停下来，后面经过和 * 倒数第二个枢纽值交换后还是一样，不影响最后i的左边都不比枢纽值大， * 右边都不比枢纽值小；如果i，j重叠时的值不是枢纽值，那么i,j必定有一个要移 * 动一个单位, i，j交错，也满足分割要求*/ if ( i < j ) swap ( &num[i], &num[j] ); else break; } /* 将原来交换的数据换回去*/ swap ( &num[i], &num[right-1] ); qsortInstance(num, left, i-1); qsortInstance(num, i+1, right); #if 0 /* 不能从middle开始，应该从最后交换结束的位置i那里作为界限, * 因为i那个位置最后被换为了原来的枢纽值, 最后枢纽值左边的 * 数都不比他大，右边的数都不比它小*/ qsort(num, left, middle); qsort(num, middle+1, right); #endif } void qsort( int num[], int size ) { qsortInstance(num, 0, size-1); } int main(int argc, char **argv) { int num[] = { 1, 4, 5, 2, 543, 42, 7,5, 42,5,3,5,4,4,3,5,5,6,7,4,4,5,6,7,8,9,5,4,5,6,7,5,5,4,6,4 }; qsort( num, sizeof(num)/sizeof(int) ); for ( int i=0; i<sizeof(num)/sizeof(int); i++ ) printf("%d ", num[i]); printf("\n"); return 0; } |