c++各种排序

1.插入排序

 1 void InsertSort(int a[], int n)
 2 {
 3     int temp, i, j;
 4     for (i = 1; i < n; i++)
 5     {
 6         if (a[i] < a[i - 1])
 7         {
 8             temp = a[i];
 9             for (j = i - 1; j >= 0 && a[j]>temp; j--)
10                 a[j + 1] = a[j];
11             a[j + 1] = temp;
12         }
13     }
14 }

View Code

时间复杂度：O（n²）

空间复杂度：O(1)

稳定性：稳定

2.希尔排序

 1 void ShellSort(int a[], int n)
 2 {
 3     int dk,temp, i, j;
 4     for (dk = n / 2; dk >= 1; dk /= 2)
 5     {
 6         for (i = dk; i <n; i+=dk)
 7         {
 8             if (a[i] < a[i - dk])
 9             {
10                 temp = a[i];
11                 for (j = i - dk; j>=0&&a[j]>temp; j -= dk)
12                     a[j + dk] = a[j];
13                 a[j + dk] = temp;
14             }
15         }
16     }
17 }

View Code

时间复杂度：O（n^1.3）

最坏时间复杂度：O（n²）

空间复杂度：O(1)

稳定性：不稳定

3.冒泡排序

 1 void BubbleSort(int a[], int n)
 2 {
 3     int temp,flag;
 4     for (int i = 1; i < n ; i++)
 5     { 
 6         flag = 0;
 7         for (int j = 0; j < n-i; j++)
 8         {
 9             if (a[j]>a[j + 1])
10             {
11                 temp = a[j];
12                 a[j] = a[j + 1];
13                 a[j + 1] = temp;
14                 flag = 1;
15             }
16         }
17         if (flag == 0) break;
18     }    
19 }

View Code

时间复杂度：O（n²）

空间复杂度：O(1)

稳定性：稳定

4.快速排序：O（nlog）---O(1)----稳定

 1 int Parttion1(int a[], int low,int high)
 2 {
 3     int temp = a[low];
 4     while (low < high)
 5     {
 6         while (low < high&&a[high] >= temp) high--;
 7         a[low] = a[high];
 8         while (low < high&&a[low] <= temp) low++;
 9         a[high] = a[low];
10     }
11     a[low] = temp;
12     return low;
13 }
14 
15 void swap(int &a, int &b)
16 {
17     int temp;
18     temp = a;
19     a = b;
20     b = temp;
21 }
22 int Parttion2(int a[], int low, int high)
23 {//将小于等于a[high]的元素移到最前面，最后再将a[high]移到最终位置
24     int temp = a[high];
25     int i = low - 1;
26     for (int j = low; j < high; j++)
27     {
28         if (a[j] <= temp)
29         {
30             i++;
31             swap(a[i], a[j]);
32         }
33     }
34     swap(a[i + 1], a[high]);
35     return i + 1;
36 }
37 void QuickSort(int a[], int low, int high)
38 {
39     if (low < high)
40     {
41         int p = Parttion2(a, low, high);
42         QuickSort(a, low, p - 1);
43         QuickSort(a, p + 1, high);
44     }
45 }

View Code

时间复杂度：O（n²）--基本有序或逆序的情况

空间复杂度：O(n)

稳定性：不稳定

平均时间复杂度最好：O（nlog₂n）

5.简单选择排序

 1 void SelectSort(int a[], int n)
 2 {
 3     int min;
 4     for (int i = 0; i < n-1; i++)
 5     {
 6         min = i;
 7         for (int j = i+1; j < n; j++)
 8         {
 9             if (a[j] < a[min])
10                 min = j;
11         }
12         if (min!=i)
13             swap(a[min], a[i]);
14     }
15 }

View Code

时间复杂度：O（n²）

空间复杂度：O(1)

稳定性：不稳定

6.堆排序

 1 void AdjustDown(int a[], int k, int n)
 2 {
 3     a[0] = a[k];  //a[0]是暂存单元
 4     for (int i = 2 * k; i <= n; i *= 2)
 5     {
 6         if (i < n&&a[i] < a[i + 1]) i++;
 7         if (a[0]>=a[i]) break;
 8         else
 9         {
10             a[k] = a[i];
11             k = i;
12         }
13     }
14     a[k] = a[0];
15 }
16 
17 void AdjustUp(int a[], int k)
18 {
19     a[0] = a[k];
20     for (int i = k / 2; i > 0; i /= 2)
21     {
22         if (a[i] > a[0]) break;
23         else
24         {
25             a[k] = a[i];
26             k = i;
27         }
28     }
29     a[k] = a[0];
30 }
31 
32 void BuildMaxHeap(int a[], int n)
33 {
34     /*for (int i = n / 2; i > 0; i--)
35         AdjustDown(a, i, n);*/
36     for (int i = n; i > 0; i--)
37         AdjustUp(a, i);
38 }
39 
40 void HeapSort(int a[], int n)
41 {
42     BuildMaxHeap(a, n);
43     for (int i = n; i > 0; i--)
44     {
45         swap(a[1], a[i]);
46         AdjustDown(a, 1, i - 1);
47     }
48 }

View Code

时间复杂度：O（nlog₂n）

空间复杂度：O(1)

稳定性：不稳定