首页 > 代码库 > 快速排序

快速排序

2024-09-03 01:26:19   220人阅读

    快速排序的基本思想是：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。

    代码：

#include<iostream>
#include<algorithm>
using namespace std;

int Quick_mid(int a[],int k,int n){
    int m = k;
    int i = k,j = n;
    while (i < j)
    {
        while (a[i] < a[m]) i++;
        while (a[j] > a[m]) j--;
        swap(a[i], a[j]);
    }
//    swap(a[i], a[j]);
//    swap(a[m], a[j]);
    return j;
}

void Quick_Sort(int a[],int low,int high){
    int m;
    if (low < high)
    {
        m = Quick_mid(a, low, high);   //找出a[m]的位置
        Quick_Sort(a, low, m-1);
        Quick_Sort(a, m + 1,high);
    }
}

int main(){
    int a[] = { 11, -5,49, 23, 6,87, 53, 18, 28, 37, 46, 36, 0,13,51, 33, 57, 42, 77 };
    int n = (sizeof(a) / sizeof(a[0]));

    Quick_Sort(a,0,n-1);
    for (int i = 0; i < n; i++)         
        cout << a[i] << ‘ ‘;
}

 

 

#include<iostream>
#include<algorithm>
using namespace std;

int Quick_mid(int a[],int k,int n){
    int m=a[k];
    int i = k,j = n;
    while (i < j)
    {
        while ((i<j)&&(a[j] >= m)) 
            j--;
        swap(a[i], a[j]);
        while ((i<j)&&(a[i] <= m))
            i++;
        swap(a[i], a[j]);
    }
    return i;
}

void Quick_Sort(int a[],int low,int high){
    int m;
    if (low < high)
    {
        m = Quick_mid(a, low, high);
        Quick_Sort(a, low, m-1);
        Quick_Sort(a, m + 1,high);
    }
}

int main(){
    int a[] = { 11, -5,49, 23, 6,87, 53, 18, 28, 37, 46, 36, 0,13,51, 33, 57, 42, 77 };
    int n = (sizeof(a) / sizeof(a[0]));

    Quick_Sort(a,0,n-1);
    for (int i = 0; i < n; i++)         
        cout << a[i] << ‘ ‘;
}

技术分享

 

快速排序


联系
我们