设有一组初始关键字序列(46,79,56,38,40,84),执行第一趟快速排序后所得序列是()
//结果应为40 38 46 56 79 84 void quickSort(SortObject *pvector,int head,int tail) { int i,j; RecordNode temp,*data=pvector->record; if(head >= tail)return; i=head;j=tail;temp=data[i]; while(i!=j) { while(i<j && data[j].key >= temp.key) j--; if(i < j) data[i++] = data[j]; while(i<j && data[j].key <= temp.key) i++; if(i<j) data[j--] = data[i]; } data[i] = temp; quickSort(pvector,head,i-1); quickSort(pvector,i+1,tail); }
void QuickSort(vector<int>& R, int start, int tail) { if (start >= tail) return; int i = start, j = tail; int tmp = R[i]; while (i < j) { while (j > i && R[j]>=tmp) { j--; } R[i] = R[j]; while (i < j && R[i]<=tmp) { i++; } R[j] = R[i]; } //此时的i和j是相等的 R[i] = tmp; showres(R); QuickSort(R, start, i-1); QuickSort(R, i+1, tail); }运算结果为:
int partition(int a[], int left, int right){ int pivot = a[left]; while(left < right){ while(left < right && a[right] >= pivot) --right; a[left] = a[right]; while(left < right && a[left] <= pivot) ++left; a[right] = a[left]; } a[left] = pivot; return left; } //partition函数通常把第一位作为pivot,对剩下的元素用前后指针来调整位置,最终将pivot归位 //最终结果为40 38 46 56 79 84