java快速排序和選擇排序實現實例解析

更新時間：2023年11月16日 10:44:16 作者：胡子拉碴的沙灘褲

這篇文章主要為大家介紹了java快速排序和選擇排序實現實例解析，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪

一、快速排序（Quick Sort）

快速排序采用分治法。首先從數列中挑出一個元素作為中間值。依次遍歷數據，所有比中間值小的元素放在左邊，所有比中間值大的元素放在右邊。然后按此方法對左右兩個子序列分別進行遞歸操作，直到所有數據有序。最理想的情況是，每次劃分所選擇的中間數恰好將當前序列幾乎等分（均勻排布），整個算法的時間復雜度為O(n logn)

最壞的情況是，每次所選的中間數是當前序列中的最大或最小元素（正序和逆序都是最壞），整個排序算法的時間復雜度為O(n²)。

平均時間復雜度為O(n logn)，空間復雜度為O(logn)，是一種不穩(wěn)定的排序算法。

附算法實現源碼：

//快速排序
template <class T>
int Partition(T data[],int left,int right)
{
    T pivot=data[left];
    while(left<right)
    {
        while(left<right&&data[right]>pivot)
            right--;
        data[left]=data[right];
        while(left<right&&data[left]<=pivot)
            left++;
        data[right]=data[left];
    }
    data[left]=pivot;
    return left;
}
template <class T>
void QuickSort(T data[],int left,int right)
{
if(left<right)
{
    int p=Partition(data,left,right);
    QuickSort(data,left,p-1);
    QuickSort(data,p+1,right);
}
}

二、、選擇排序（Selection Sort）

遍歷所有數據，先在數據中找出最大或最小的元素，放到序列的起始；然后再從余下的數據中繼續(xù)尋找最大或最小的元素，依次放到序列中直到所有數據有序。原始數據的排列順序不會影響程序耗費時間O(n²)，相對費時，不適合大量數據排序。

平均時間復雜度為O(n²)，空間復雜度為O(1)，是一種不穩(wěn)定的排序算法。

附算法實現源碼：

//選擇排序
template <class T>
void SelectionSort(T data[],int n)
{
    for(int i=1;i<n;i++)
    {
        int k=i-1;
        for(int j=i;j<n;j++)
        {
            if(data[j]<data[k])
            {
                k=j;
            }
        }
        if(k!=i-1)
        {
            T t=data[k];
            data[k]=data[i-1];
            data[i-1]=t;
        }
    }
}

三、插入排序（Insertion Sort）

將前i個（初始為1）數據假定為有序序列，依次遍歷數據，將當前數據插入到前述有序序列的適當位置，形成前i+1個有序序列，依次遍歷完所有數據，直至序列中所有數據有序。數據是反序時，耗費時間最長O(n²)；數據是正序時，耗費時間最短O(n)。適用于部分數據已經排好的少量數據排序。

平均時間復雜度為O(n²)，空間復雜度為O(1)，是一種穩(wěn)定的排序算法。

附算法實現源碼（直接插入+折半插入）：

//直接插入排序
template <class T>
void InsertionSort(T Data[],int n)
{
    int p,i;
    for(p=1;p<n;p++)
    {
        T temp=Data[p];
        i=p-1;
        while(i>=0&&Data[i]>temp)
        {
            Data[i+1]=Data[i];
            i--;
        }
        Data[i+1]=temp;
    }
}
//折半插入排序
template <class T>
void BinaryInsertionSort(T Data[],int n)
{
    int left,mid,right,p;
    for(p=1;p<n;p++)
    {
        T temp=Data[p];
        left =0;
        right=n-1;
        while(left<=right)
        {
            mid=(left+right)/2;
            if(Data[mid]>temp)
                right=mid-1;
            else
                left=mid+1;
        }
        for(int i=p-1;i>=left;i--)
            Data[i+1]=Data[i];
        Data[left]=temp;
    }
}

四、希爾排序（Shell Sort）

希爾排序也稱遞減增量排序，是對插入排序的改進，以犧牲穩(wěn)定性的方法提高效率。基本思路是先將整個數據序列分割成若干子序列分別進行直接插入排序，待整個序列中的記錄基本有序時，再對全部數據進行依次直接插入排序，直至所有數據有序。希爾排序算法的性能與所選取的分組長度序列有很大關系，復雜度下界為O(n log²n)，在中等規(guī)模的數據中表現良好。

平均時間復雜度為O(n^3/2)，空間復雜度為O(1)，是一種不穩(wěn)定的排序算法。

附算法實現源碼：

//希爾排序
template <class T>
void ShellSort(T Data[],int n)
{
    int d=n/2;
    while(d>=1)
    {
        for(int k=0;k<d;k++)
        {
            for(int i=k+d;i<n;i+=d)
            {
                T temp=Data[i];
                int j=i-d;
                while(j>=k&&Data[j]>temp)
                {
                    Data[j+d]=Data[j];
                    j-=d;
                }
                Data[j+d]=temp;
            }
        }
        d=d/2;
    }
}

以上就是java快速排序和選擇排序實現實例解析的詳細內容，更多關于java快速排序選擇排序的資料請關注腳本之家其它相關文章！

您可能感興趣的文章: