冒泡排序算法以及改进

2019-11-08 02:19:42

字体：大中小

来源：转载

供稿：网友

为了能给老是忘记的自己做个笔记。

冒泡排序（升序）的思想就是将最大的数逐步后移，例如：arr[n] ={5, 9, 8, 6, 7},i从数组下标0开始，j从数组下标n-1开始，依次将arr[j]与arr[j-1]比较，如果arr[j] < arr[j-1]就将arr[j]与arr[j-1]交换，直到j = i;

C++代码：

#include <iostream>using namespace std;void swap(int *a, int *b){ int t; t = *a; *a = *b; *b = t;}void sort(int p[], int n){ for(int i = 0; i < n; i++){ for(int j = n-1; j > i; j--){ if(p[j] < p[j-1]){ swap(&p[j], &p[j-1]); } } } for(int i = 0; i < n; i++){ cout << p[i] <<" "; }}int main(){ int n, *p; cin >> n; p = new int[n]; for(int i = 0; i < n; i++){ cin >> p[i]; } sort(p, n); return 0;}

改进：设置bool型变量temp，当上一次循环没有交换元素则证明排序已经完成，无需进行下一次排序，直接跳出循环。

C++代码：

#include<iostream>using namespace std;void swap(int *a, int *b){ int t; t = *a; *a = *b; *b = t;}void sort(int p[], int n){ bool temp; //设置变量，如果上次循环没有交换则停止排序 for(int i = 0; i < n; i++){ temp = 0; for(int j = n-1; j > i; j--){ if(p[j] < p[j-1]){ temp = 1; swap(&p[j], &p[j-1]); } } if(temp == 1) break; } for(int i = 0; i < n; i++){ cout << p[i] <<" "; }}int main(){ int n, *p; cin >> n; p = new int[n]; for(int i = 0; i < n; i++){ cin >> p[i]; } sort(p, n); return 0;}

上一篇：POSIX多线程编程(二)

下一篇：nyoj 145 聪明的小珂