冒泡排序之改进算法直接上代码参考上篇冒泡排序易懂

             1
            //
            在传统冒泡中，每一轮外循环都会导致将该循环中最大的数沉底，会导致内循环从0到最后一个数之间

             2
            //
            每俩个数俩俩比较，如果在某一趟外循环中，内循环的Swap()函数没有执行过一次，那就代表此时从前

             3
            //
            到最后已经是有序的了，此时直接退出循环即可。
             4
             5
             6 #include<iostream>
 7 #include<time.h>
 8 #include<stdlib.h>
 9 #include<sys/timeb.h>
10usingnamespace std;
1112constint Max = 10;
13bool flag = false;//表示没有排序好。1415void swap(int& a, int& b) {
16int temp = a;
17     a = b;
18     b = temp;
19}
20//小数冒泡
21//void Maopaosort(int* arr,int length) {
22//    for (int i = 0; i < length-1; i++) {
23//        for (int j = length-1; j>i; j--) {     
24//            if (arr[j-1] > arr[j]) 
25//                swap(arr[j], arr[j - 1]);
26//        }
27//    }
28//}
29//大数沉底3031void Maopaosort(int* arr, int length) {
32for (int i = 0; i < length - 1 && flag==false; i++) {
33         flag = true;  //假设上一次排序后，已经完全有序了，如果这一轮排序没有发生内循环交换，表明真的有序则退出循环。34for (int j = 0; j < length - i - 1; j++) {
35if (arr[j] > arr[j + 1]) {
36                 swap(arr[j], arr[j + 1]);
37                 flag = false; //表示在这一趟中发生了交换，则表示上一趟排序结果依然没有完全有序，但是也不能保证这一趟就完全有序了38            }
3940        }
41    }
42}
434445long getSystemTime() {
46struct timeb tb;
47     ftime(&tb);
48return tb.time * 1000 + tb.millitm;
49}
50void Print(constint* arr, int length) {
51for (int i = 0; i < length; i++) {
52         cout << arr[i] << "";
53    }
5455}
56int main() {
57int arr[Max];
58    srand((unsigned)time(NULL));
59for (int i = 0; i < Max; i++) {
60         arr[i] = rand() % Max;
61    }
62     cout << "排序前：\n";
63    Print(arr, Max);
64long pt = getSystemTime();
65    Maopaosort(arr, Max);
66long at = getSystemTime();
67     cout << "\n排序后：\n";
68    Print(arr, Max);
6970     cout << "\ntime of sort:" << at - pt << "ms\n";
717273return0;
74 }