【排序】冒泡排序+快速排序

冒泡排序：

 1 //复杂度：O(n^2)
 2 //比较次数：n*(n-1)/2 ；移动等数量级
 3 #include<iostream>
 4 #include<cstdio>
 5 #include<cstdlib>
 6 using namespace std;
 7 const int INF = 0x7fffffff;
 8 void Bubble_sort(int* A, int n)
 9 {
10     for(int i = n-1; i >= 0; i--)
11     {
12         A[n] = A[i];
13         int _max = -INF, pos = -1;
14         for(int j = 0; j <= i; j++)
15         {
16             if(_max < A[j]) _max = A[j], pos = j;
17         }
18         A[pos] = A[n];
19         A[i] = _max;
20     }
21     for(int i = 0; i < n; i++)  {if(i) printf(" "); printf("%d", A[i]);}
22     printf("
");
23 }
24 
25 int main()
26 {
27     int A[10] = {1, 9, 3, 7, 5, 2, 8, 4, 6, 10};
28     Bubble_sort(A, 10);
29     return 0;
30 }

View Code

快速排序：

 1 //一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，
 2 //则可分别对这两部分记录继续进行排序，以达到整个序列有序
 3 //复杂度：O(nlnn)
 4 #include<iostream>
 5 #include<cstdio>
 6 #include<cstdlib>
 7 #include<list>
 8 using namespace std;
 9 //改进前
10 //void Exchange(int* L, int i, int j)
11 //{
12 //    int tmp = L[i]; L[i] = L[j]; L[j] = tmp;
13 //}
14 
15 int Partition(int* L, int low, int high){
16     L[0] = L[low];
17     int pivotkey = L[low];
18     while(low < high)
19     {
20         while(low < high && L[high] >= pivotkey) high--;
21         //Exchange(L, low, high);
22         L[low] = L[high];
23         while(low < high && L[low] <= pivotkey) low++;
24         //Exchange(L, low, high);
25         L[high] = L[low];
26     }
27     L[low] = L[0];
28     return low;//返回枢轴所在位置
29 }
30 void Quick_sort(int* L, int low, int high)
31 {
32     if(low >= high)  return ;
33     int pivotkey = Partition(L, low, high);
34     Quick_sort(L, low, pivotkey-1);
35     Quick_sort(L, pivotkey+1, high);
36 }
37 
38 int main()
39 {
40     int L[11] = {0, 3, 9, 1, 7, 5, 2, 8, 4, 6, 10};
41     Quick_sort(L, 1, 10);
42     for(int i = 1; i <= 10; i++) {if(i) printf(" "); printf("%d", L[i]);}
43     printf("
");
44     return 0;
45 }