快捷導(dǎo)航

java快速排序和選擇排序?qū)崿F(xiàn)實例解析

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

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

一、快速排序（Quick Sort）

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

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

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

附算法實現(xià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）

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

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

附算法實現(xià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）數(shù)據(jù)假定為有序序列，依次遍歷數(shù)據(jù)，將當(dāng)前數(shù)據(jù)插入到前述有序序列的適當(dāng)位置，形成前i+1個有序序列，依次遍歷完所有數(shù)據(jù)，直至序列中所有數(shù)據(jù)有序。數(shù)據(jù)是反序時，耗費時間最長O(n²)；數(shù)據(jù)是正序時，耗費時間最短O(n)。適用于部分?jǐn)?shù)據(jù)已經(jīng)排好的少量數(shù)據(jù)排序。

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

附算法實現(xià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）

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

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

附算法實現(xià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快速排序和選擇排序?qū)崿F(xiàn)實例解析的詳細(xì)內(nèi)容，更多關(guān)于java快速排序選擇排序的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: