各种排序总结

代码中所有数组都是 1~n。

1、冒(起)泡排序

1 void sort1( int a[],int n)
2 {
3     for(int i=1; i<=n-1; i++)
4         for(int j=1; j<=n-i; j++)
5             if(a[j+1]<a[j])
6                 swap(a[j],a[j+1]);
7 }

C++

2、选择排序

 1 void sort2(int a[],int n)
 2 {
 3     for(int i=1;i<=n;i++)
 4     {
 5         int k=i;
 6         for(int j=i;j<=n;j++)
 7         if(a[j]<a[i])
 8         k=j;
 9         swap(a[k],a[i]);
10     }
11 }

C++

3、归并排序

 1 void Merge(int *a,int l,int m,int r)
 2 {
 3     //将两个有序的子数组R[l,m)和R[m+1,r]归并成一个有序 R[l,r]
 4     int cnt1=l;
 5     int cnt2=m+1;
 6     int k=1;
 7     int s[r-l+5];//大小自定
 8     while(cnt1<=m&&cnt2<=r)
 9         s[k++]=a[cnt1]>a[cnt2]? a[cnt2++]:a[cnt1++];
10     while(cnt1<=m)
11         s[k++]=a[cnt1++];
12     while(cnt2<=r)
13         s[k++]=a[cnt2++];
14     for(int i=l; i<=r; i++)
15         a[i]=s[i-l+1];
16 }
17 void Merge_sort(int a[],int l,int r)
18 {
19     if(l<r)
20     {
21         int m=(l+r)/2;
22         Merge_sort(a,l,m);
23         Merge_sort(a,m+1,r);
24         Merge(a,l,m,r);
25     }
26 }

C++（1）

1 void sort3(int *a,int n)
2 {
3     for(int cnt=2; cnt/2<n; cnt*=2) //每次的排序间隔
4         for(int i=1; i<=n; i+=cnt)
5             sort(a+i,a+min(cnt+i,n+1));
6 }

C++（2）

第二个是看别人的博客的，忘记在哪了，应该不是归并，我也不知道是啥

4、插入排序

把n个待排序的元素看成为一个有序表和一个无序表。开始时有序表中只包含1个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。

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

View Code

5、快速排序

快速排序算法：我们通常采用某种方法取一个元素作为主元，通过交换，把比主元小的元素放到它的左边，比主元大的元素放到它的右边。

 1 void quick_sort(int *a,int l,int r)
 2 {
 3     if(l<r)
 4     {
 5         int i,j,tmp;
 6         i=l;
 7         j=r;
 8         tmp=a[i];
 9         while(i<j)
10         {
11             while(i<j&&a[j]>tmp)
12                 j--;// 从右向左找第一个小于x的数
13             if(i<j)
14                 a[i++]=a[j];
15             while(i<j&&a[i]<tmp)
16                 i++;// 从左向右找第一个大于x的数
17             if(i<j)
18                 a[j--]=a[i];
19         }
20         a[i]=tmp;
21         quick_sort(a,l,i-1);
22         quick_sort(a,i+1,r);
23     }
24 }
25 
26 C++（递归）

View Code

6、堆排序

 1 void max_heapify(int num[], int i, int last)
 2 {
 3     int index;
 4     if(2 * i + 2 <= last){
 5         if(num[2 * i + 1] < num[2 * i + 2]){
 6             index = 2 * i + 2;    
 7         }    
 8         else{
 9             index = 2 * i + 1;    
10         }
11         if(num[i] < num[index]){
12             swap(num[i], num[index]);    
13             max_heapify(num, index, last);
14         }
15     }    
16     else if(2 * i + 1 <= last){
17         if(num[2 * i + 1] > num[i]){
18             swap(num[i], num[2 * i + 1]);    
19         }    
20     }
21 }
22 
23 void build_maxheap(int num[], int n)
24 {
25     for(int i = n - 1; i >= 0; i --){
26         max_heapify(num, i, n - 1);    
27     }    
28 }
29 
30 void heapsort(int num[], int n)
31 {
32     build_maxheap(num, n);    
33     for(int i = n - 1; i > 0; i --){
34         swap(num[0], num[i]);    
35         max_heapify(num, 0, i - 1);
36     }
37 }

C++

 1 void heapify(int arr[], int n, int i){
 2     if(i >= n) return ;
 3     int l = 2 * i + 1;
 4     int r = 2 * i + 2;
 5     int max = i;
 6     if(l < n && arr[l] > arr[max]) max = l;
 7     if(r < n && arr[r] > arr[max]) max = r;
 8     if(max != i){
 9         swap(arr[i], arr[max]);
10         heapify(arr, n, max); //max代表的就是左右孩子的下标 
11     }
12 }
13 void heapSort(int arr[], int n){
14     int last_node = n - 1;
15     int parent = (last_node - 1) / 2;
16     
17     for(int i = parent; i >= 0; i--){ //调整堆 
18         heapify(arr, n, i);
19     }
20     for(int i = n - 1; i >= 0; i--){
21         swap(arr[0], arr[i]);
22         heapify(arr, i, 0); //0~i之间的数进行调整 
23     } 
24 } 
25 ————————————————
26 版权声明：本文为CSDN博主「姚军博客」的原创文章，遵循 CC 4.0 BY 版权协议，转载请附上原文出处链接及本声明。
27 原文链接：https://blog.csdn.net/SYaoJun/article/details/99694077

View Code