快速排序算法及其優化方法

1、基本快速排序

class QuickSort {
public:
    void swap(int a[],int i,int j){
        int temp=a[i];
        a[i]=a[j];
        a[j]=temp;
    }

    int partition(int a[],int low,int high){
        int key=a[low];
        while(low<high){
            //注意以下語句1語句2和語句3語句4的位置不能颠倒，另外語句1和語句3中帶有的等号注意别丢失
while(low<high&&a[high]>=key){high--;} //語句1
            swap(a,low,high); //語句2

            while(low<high&&a[low]<=key){low++;} //語句3
            swap(a,low,high);//語句4
        } 
        return low;
    }

    void qSort(int a[],int low,int high){
        if(low<high){
            int key=partition(a,low,high);
            qSort(a,low,key-);
            qSort(a,key+,high);
        }
    }
    int* quickSort(int* A, int n) {
        // write code here
        int low=,high=n-;

        qSort(A,low,high);
        return A;
    }
};
           

2、速排序算法改進一（三數取中法）

對于快速排序的基本算法，其中取劃分值并不一定都能取得最優，不一定每次取得都是中間大小元素，故而對于類似數組a[10]={9,8,7,6,5,4,3,2,1,0}這樣的數組效率很低，采用三數取中間大小的方法（每次都取數組最低位置，中間位置，最高位置的三個元素中中間大小的元素作為劃分值）對該算法進行優化。

class QuickSort {
public:
    void swap(int a[],int i,int j){
        int temp=a[i];
        a[i]=a[j];
        a[j]=temp;
    }

int partition(int a[],int low,int high){
    //以下采用三叔取中法對快速排序進行優化
    //注意：和間為新增代碼
        int mid=low+(high-low)/;
        if(a[high]>a[low]){
            swap(a,low,high);
        }        
        if(a[high]>a[mid]){
            swap(a,high,mid);
        }
        if(a[mid]>a[low]){
            swap(a,low,mid);
        }
        int key=a[low];
        ////
        while(low<high){
            while(low<high&&a[high]>=key){high--;}
            swap(a,low,high);
            while(low<high&&a[low]<=key){low++;}
            swap(a,low,high); 
        } 
        return low; 
    }

    void qSort(int a[],int low,int high){
        if(low<high){
            int key=partition(a,low,high);
            qSort(a,low,key-);
            qSort(a,key+,high);
        }
    }
    int* quickSort(int* A, int n) {
        // write code here

        qSort(A,,n-);
        return A;
    }
};
           

3、快速排序算法改進二（減少劃分值不必要的交換）

該優化方法是通過采用直接指派的方法進而減少劃分值不必要的交換次數，進而達到優化的效果

class QuickSort {
public:
    void swap(int a[],int i,int j){
        int temp=a[i];
        a[i]=a[j];
        a[j]=temp;
    }

    int partition(int a[],int low,int high){
        int mid=low+(high-low)/;
        if(a[high]>a[low]){
            swap(a,low,high);
        }        
        if(a[high]>a[mid]){
            swap(a,high,mid);
        }
        if(a[mid]>a[low]){
            swap(a,low,mid);
        }
        int key=a[low];
        while(low<high){
            while(low<high&&a[high]>=key){high--;}
            a[low]=a[high]; //采用直接複制故而可以減少劃分值不必要的交換
            while(low<high&&a[low]<=key){low++;}
            a[high]=a[low];
        } 
        a[low]=key;//将劃分值放置
        return low; 
    }

    void qSort(int a[],int low,int high){
        if(low<high){
            int key=partition(a,low,high);
            qSort(a,low,key-);
            qSort(a,key+,high);
        }
    }
    int* quickSort(int* A, int n) {
        // write code here
        qSort(A,,n-);
        return A;
    }
};
           

4、快速排序算法改進三

優化小數組時的方案，快速排序存在遞歸，對于大規模的資料采用快速排序的方法能産生很好的時間效率，但對于規模很小的數組，則采用快速排序很浪費。直接插入排序是簡單排序中效率最好的，是以對于小規模的數組，采用直接插入排序。快速排序和插入排序結合使用可以達到很好的效果。

class QuickSort {
public:
void iSort(int a[],int n)
{
        int i,j,temp;
        for(i=;i<n;i++)
        {
            if(a[i-]>a[i])
            {
                j=i-;
                temp=a[i];
                while(j>=&&a[j]>temp)
                {
                    a[j+]=a[j];
                    j--;
                }
                a[j]=temp;
            }
        }
}

void insertSort(int a[],int low,int high)
{
        iSort(a+low,high-low+);
}

    void swap(int a[],int i,int j){
        int temp=a[i];
        a[i]=a[j];
        a[j]=temp;
    }

    int partition(int a[],int low,int high){
        int mid=low+(high-low)/;
        if(a[high]>a[low]){
            swap(a,low,high);
        }        
        if(a[high]>a[mid]){
            swap(a,high,mid);
        }
        if(a[mid]>a[low]){
            swap(a,low,mid);
        }
        int key=a[low];
        while(low<high){
            while(low<high&&a[high]>=key){high--;}
            a[low]=a[high]; //采用直接複制故而可以減少劃分值不必要的交換
            while(low<high&&a[low]<=key){low++;}
            a[high]=a[low];
        } 
        a[low]=key;//将劃分值放置
        return low; 
    }

    void qSort(int a[],int low,int high){
        if((high-low)>MAX_LENGTH_INSERTSORT)
        {
            int key=partition(a,low,high);
            qSort(a,low,key-);
            qSort(a,key+,high);
        }
        else
        {
            insertSort(a,low,high);
        }       
}

    int* quickSort(int* A, int n) {
        // write code here
        qSort(A,,n-);
        return A;
    }
};
           

5、快速排序算法改進四

對于快速排序存在兩次遞歸操作，很浪費時間和空間，故通過減少遞歸操作可大大節約時間和空間，采用尾遞歸的方式，尾遞歸介紹如下：

對于尾遞歸，編譯器可以對其進行自動優化！！！

class QuickSort {
public:
void iSort(int a[],int n)
{
        int i,j,temp;
        for(i=;i<n;i++)
        {
            if(a[i-]>a[i])
            {
                j=i-;
                temp=a[i];
                while(j>=&&a[j]>temp)
                {
                    a[j+]=a[j];
                    j--;
                }
                a[j]=temp;
            }
        }
}

void insertSort(int a[],int low,int high)
{
        iSort(a+low,high-low+);
}

    void swap(int a[],int i,int j){
        int temp=a[i];
        a[i]=a[j];
        a[j]=temp;
    }

    int partition(int a[],int low,int high){
        int mid=low+(high-low)/;
        if(a[high]>a[low]){
            swap(a,low,high);
        }        
        if(a[high]>a[mid]){
            swap(a,high,mid);
        }
        if(a[mid]>a[low]){
            swap(a,low,mid);
        }
        int key=a[low];
        while(low<high){
            while(low<high&&a[high]>=key){high--;}
            a[low]=a[high]; //采用直接複制故而可以減少劃分值不必要的交換
            while(low<high&&a[low]<=key){low++;}
            a[high]=a[low];
        } 
        a[low]=key;//将劃分值放置
        return low; 
    }

    void qSort(int a[],int low,int high){
        if((high-low)>MAX_LENGTH_INSERTSORT)
        {
            while(low<high)
            {
                int key=partition(a,low,high);
                if(key-low<high-key)//将左數組和右數組長度小的進行遞歸
                {
                    qSort(a,low,key-);
                    //qSort(a,key+,high);
                    low=key+;
                }
                else
                {
                    qSort(a,key+,high);
                    high=key-;
                }
        }       
        else
        {
            insertSort(a,low,high);
        }       
}

    int* quickSort(int* A, int n) {
        // write code here
        qSort(A,,n-);
        return A;
    }
};