快速排序的算法C++实现
发布时间:2020-12-16 07:48:12 所属栏目:百科 来源:网络整理
导读:今天PHP站长网 52php.cn把收集自互联网的代码分享给大家,仅供参考。 #include stdio.h#include stdlib.h#define SORT_ARRAY_SIZE 10000#define PIVOT_FIRST 1#define PIVOT_LAST 0#define PIVOT_MEDIAN_OF_THREE 0void Q
以下代码由PHP站长网 52php.cn收集自互联网 现在PHP站长网小编把它分享给大家,仅供参考 #include <stdio.h> #include <stdlib.h> #define SORT_ARRAY_SIZE 10000 #define PIVOT_FIRST 1 #define PIVOT_LAST 0 #define PIVOT_MEDIAN_OF_THREE 0 void QuickSort(int *array,int start,int end); int ChoosePivot(int *array,int end); static long long compNum = 0; int main() { // load txt into array buffer int *array = (int*)malloc(sizeof(int)*SORT_ARRAY_SIZE+10); FILE *pFile; pFile = fopen("QuickSort.txt","r"); if (pFile == NULL) perror("Error openin file.n"); rewind(pFile); for (int i = 0; i < SORT_ARRAY_SIZE; i++) { fscanf(pFile,"%d",&array[i]); } fclose(pFile); // quick sort array QuickSort(array,SORT_ARRAY_SIZE-1); printf("number of comparisons is %lldn",compNum); free(array); return 0; } void QuickSort(int *array,int end) { if (start >= end) return; else if ((end - start == 1)&&(array[start]>array[end])) { compNum += 1; int temp = array[start]; array[start] = array[end]; array[end] = temp; } else { compNum += (end - start); // choose the pivot and do proper swap int pivot = ChoosePivot(array,start,end); // i denotes the location of pivot int i = start + 1; // j for loop the unpartitioned part for (int j = start + 1; j < end + 1; j++) { if (array[j] < pivot) { int temp = array[j]; array[j] = array[i]; array[i] = temp; i++; } } // swap the pivot and array[i-1] int temp = array[i-1]; array[i-1] = pivot; array[start] = temp; // quick sort the left and right partition QuickSort(array,i-2); QuickSort(array,i,end); } } int ChoosePivot(int *array,int end) { int pivot = -1; #if PIVOT_FIRST // choose the first element as pivot pivot = array[start]; return pivot; #elif PIVOT_LAST // choose the last element as pivot // swap the first and the last element pivot = array[end]; array[end] = array[start]; array[start] = pivot; return pivot; #elif PIVOT_MEDIAN_OF_THREE // choose the median of first,mid and last // element as pivot int mid = (start + end) / 2; int max = (array[start] > array[end]) ? (array[start]) : (array[end]); max = (max > array[mid]) ? max : array[mid]; int min = (array[start] < array[end]) ? (array[start]) : (array[end]); min = (min < array[mid]) ? min : array[mid]; if (array[start] != max && array[start] != min) { pivot = array[start]; return pivot; } if (array[mid] != max && array[mid] != min) { pivot = array[mid]; array[mid] = array[start]; array[start] = pivot; return pivot; } if (array[end] != max && array[end] != min) { pivot = array[end]; array[end] = array[start]; array[start] = pivot; return pivot; } #endif } 以上内容由PHP站长网【52php.cn】收集整理供大家参考研究 如果以上内容对您有帮助,欢迎收藏、点赞、推荐、分享。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |