C/C++十大排序大总结

嘉岳呀

C/C++十大排序大总结

1.BubbleSort冒泡排序

  | 定义：在同一个数组中，从数组第一个数开始，相邻两个数进行比较，按照小左大右或者大右小左的顺序，依次循环遍历，进行排序

1. void BubbleSort(int *arr,int Length)
   
2. {
   
3.     int i = 0;
   
4.     int j = 1;
   
5.     int sys = 0;
   
6.     for (i = 0; i < Length-1; i++)
   
7.     {
   
8.         for (j = 0; j < Length-i-1; j++)
   
9.         {
   
10.             if (arr[j]>arr[j+1])
    
11.             {
    
12.                 arr[j] = arr[j]^arr[j+1];
    
13.                 arr[j+1] = arr[j]^arr[j+1];
    
14.                 arr[j] = arr[j]^arr[j+1];
    
15.             }
    
16. 
    
17.         }
    
18.         sys++;
    
19.     }
    
20. }

复制代码

改进版冒泡排序

在原有的基础上，我们添加了标记，记录了最后一次交换的位置

如5，1，4，6，3，2，7，8，9。最后一次交换的位置在2处，并且设定我们每次循环的到2，不对7，8，9

进行比较，节省我们运算的效率！

  | 冒泡排序是对全部已经排好序列排序最快的

1. void BetterBubbleSort(int *arr,int Length)
   
2. {
   
3.     int i = 0;
   
4.     int j = 1;
   
5.     int pmark;
   
6.     int sys = 0;
   
7.     for (; i < Length-1; i++)
   
8.     {
   
9.         pmark = 0;
   
10.         for (j = 0; j < Length-i-1; j++)
    
11.         {
    
12.             if (arr[j]>arr[j+1])
    
13.             {
    
14.                 arr[j] = arr[j]^arr[j+1];
    
15.                 arr[j+1] = arr[j]^arr[j+1];
    
16.                 arr[j] = arr[j]^arr[j+1];
    
17.                 pmark = j+1;
    
18.             }
    
19. 
    
20.         }
    
21. 
    
22.         i == Length - pmark - 1;
    
23.         sys++;
    
24.     }
    
25. }

复制代码

不带中间变量实现两个相同类型不同值变量间的互换

1.加减法

1. int a = 5;
   
2. int b = 3;
   
3. a = a+b;
   
4. b = a-b;
   
5. a = a-b;

复制代码

2.异或^

1. int a = 5;
   
2. int b = 3;
   
3. a = a^b;
   
4. b = a^b;
   
5. a = a^b;

复制代码

  | ps:若对于*a，*b值进行交换，*a，*b不能指向同一块地址空间！

未完……