排序算法的一点小心得

发布于 2019-01-09  741 次阅读


手写了两种排序算法,但是写快排的时候,数据一大就开始死循环

原来是我判断循环跳出条件那个地方出了一点问题,cmp函数里面我写的时候当a<b时才返回真,而当a==b时,程序会认为两个元素需要交换,从而无限次地交换,死循环

一句话总结:快排一定要 跳过两个元素相等的情况

#include<cstdio>
#include<ctime>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int MAX = 100000;
int a[MAX];

bool cmp(int a, int b){
    return a < b;
}

void set_array(int n){
    for(int i = 1; i <= n; i++)
        a[i] = rand() % 100;
}

void print(int n){
    for(int i = 1; i <= n; i++)
        printf("%d ", a[i]);
    printf("\n\n");
}

void bubble_sort(int n){
    for(int i = 1; i <= n - 1; i++)
        for(int j = 1; j <= n - i; j++)
            if(!cmp(a[j], a[j + 1])) swap(a[j], a[j + 1]);
}

void quick_sort(int s, int e){
    if(s >= e ) return;
    int i = s, j = e;
    while(i < j){
    /*
    下方while中,如果两个元素相等,必须跳过,因为一旦不跳过
    程序将陷入死循环 
    即加上 a[i]==a[j]
    */
        while(i < j && cmp(a[i], a[j]) || a[i] == a[j]) j--;
        swap(a[i], a[j]);
        while(i < j && cmp(a[i], a[j]) || a[i] == a[j]) i++;
        swap(a[i], a[j]);
    }
    quick_sort(s, i-1);
    quick_sort(i+1, e);
}

int main(){
    srand(time(NULL));
    int n,CHOICE;
    scanf("%d",&n);
    set_array(n);
    print(n);

    scanf("%d",&CHOICE);
    switch(CHOICE){
        case 1:{
            bubble_sort(n);
            break;
        }
        case 2:{
            quick_sort(1, n);
            break;
        }
    }
    print(n);

}

CTFer|NOIPer|CSGO|摸鱼|菜鸡