初音ミクの消失

排序算法的一点小心得

字数统计: 386阅读时长: 1 min
2019/01/09 Share

手写了两种排序算法,但是写快排的时候,数据一大就开始死循环 原来是我判断循环跳出条件那个地方出了一点问题,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);

}

原文作者:mrh929

原文链接:https://mrh1s.top/posts/e0221437/

发表日期:January 9th 2019, 3:01:14 pm

更新日期:May 8th 2019, 10:21:38 pm

版权声明:本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG