快速排序的算法C++实现

概述快速排序的算法C++实现

下面是内存溢出 jb51.cc 通过网络收集整理的代码片段。

内存溢出小编现在分享给大家，也给大家做个参考。

#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 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 %lld\n",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}

以上是内存溢出(jb51.cc)为你收集整理的全部代码内容，希望文章能够帮你解决所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。

总结

以上是内存溢出为你收集整理的快速排序的算法C++实现全部内容，希望文章能够帮你解决快速排序的算法C++实现所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。