C/C++ 排序算法总结

1.冒泡排序

https://blog.csdn.net/weixin_49303682/article/details/119365319

1 #include <stdio.h>2 3 #define N 94 5 void print(int a[])6 {7     for(int i = 0; i < N; i++)8     {9         printf("%d ", a[i]);
10     }
11         printf("\n");
12 }
13  
14 void maopao(int a[])
15 {
16     int i, j;
17     for (i = 0; i < N -1; i++)
18     {
19         for (j = 0; j < N -1 -i; j++) 
20         {
21             if (a[j] > a[j + 1])
22             {
23                  int temp = a[j];
24                  a[j] = a[j+1];
25                  a[j+1] = temp;
26             }
27         }
28     }
29 }
30  
31 int main()
32 {
33     int a[] = {9,3,1,4,2,7,8,6,5};
34     maopao(a);
35     print(a);
36     
37     return 0;
38 }

2.选择排序

https://blog.csdn.net/weixin_49303682/article/details/119429850

1 #include <stdio.h>2 3 #define N 94 5 void print(int a[])6 {7     for(int i = 0; i < N; i++)8     {9         printf("%d ", a[i]);
10     }
11         printf("\n");
12 }
13  
14 void xuanze(int a[])
15 {
16     int i, j,min,temp;
17     for(i=0;i<N;i++)
18     {
19         min=i;    
20         for(j=i+1;j<N;j++)  
21         {
22             if(a[j]<a[min])    
23             {
24                 min=j;
25             }else{
26                 break;
27             }
28         }
29         temp=a[min];    
30         a[min]=a[i];  
31         a[i]=temp;
32     }
33 }
34  
35 int main()
36 {
37     int a[] = {9,3,1,4,2,7,8,6,5};
38     xuanze(a);
39     print(a);
40     
41     return 0;
42 }

3.直接插入排序

https://blog.csdn.net/weixin_49303682/article/details/119430023

1 #include <stdio.h>2 3 #define N 94 5 void print(int a[])6 {7     for(int i = 0; i < N; i++)8     {9         printf("%d ", a[i]);
10     }
11         printf("\n");
12 }
13  
14 void xuanze(int a[])
15 {
16     int i,j,tmp;
17     for(i = 1;i < N;i++){
18         tmp = a[i];
19         for(j = i-1; j >= 0;j--)
20         {
21             if(tmp < a[j])
22             {
23                 a[j+1] = a[j];
24             }else{
25                 break;
26             } 
27         }
28         a[j+1] = tmp;
29     }
30 }
31  
32 int main()
33 {
34     int a[] = {9,3,1,4,2,7,8,6,5};
35     xuanze(a);
36     print(a);
37     
38     return 0;
39 }

4.shell排序

https://blog.csdn.net/weixin_49303682/article/details/119364710

1 #include <stdio.h>2 3 #define N 94 5 void print(int a[])6 {7     for(int i = 0; i < N; i++)8     {9         printf("%d ", a[i]);
10     }
11         printf("\n");
12 }
13  
14 void shell(int a[])
15 {
16     int i,j,d,tmp;
17     for(d = N/2; d > 0; d /= 2)
18     {
19         for(i = d;i < N;i++)
20         {
21            tmp = a[i];
22            for(j = i-d; j >= 0;j-=d)
23            {
24               if(tmp < a[j])
25               {
26                  a[j+d] = a[j];
27               }else{
28                   break;
29               } 
30            }
31            a[j+d] = tmp;
32         }
33     }
34 }
35  
36 int main()
37 {
38     int a[] = {9,3,1,4,2,7,8,6,5};
39     shell(a);
40     print(a);
41     
42     return 0;
43 }

5.快速排序

https://blog.csdn.net/weixin_49303682/article/details/119364992

1 #include <stdio.h>2 3 #define N 94 5 void print(int a[])6 {7     for(int i = 0; i < N; i++)8     {9         printf("%d ", a[i]);
10     }
11         printf("\n");
12 }
13  
14 int kuaisu(int a[],int i,int j)
15 {
16     int tmp;
17     tmp = a[i];   //将a[i]作为基准保存
18     while(i < j)
19     {
20         while(i < j && tmp < a[j])
21             j--;
22         if(i < j)
23             a[i] = a[j];
24         while(i < j && tmp > a[i])
25             i++;
26         if(i < j)
27             a[j] = a[i];
28     }
29     a[i] = tmp;    
30     return i; 
31 }
32 
33 void digui(int a[],int i,int j)
34 {
35     int mid;
36     if(i < j)
37     {
38         mid = kuaisu(a,i,j);    
39         digui(a,i,mid-1);   
40         digui(a,mid+1,j);  
41     }
42 }
43  
44 int main()
45 {
46     int a[] = {9,3,1,4,2,7,8,6,5};
47     digui(a,0,N-1);
48     print(a);
49     
50     return 0;
51 }

6.二分查找（有序数组）

https://blog.csdn.net/qq_63918780/article/details/122527681

1 #include <stdio.h>2 #include <string.h>3 4 int func(int *a,int j,int x)5 {6     int len = j - 1,i = 0,min;7     while(i<j)8     {9        min = (i+len)/2;
10        if(min > x)
11        {
12           len = min-1;
13        }
14        else if(min < x)
15        {
16           i = min+1;
17        }
18        else
19        {
20           break;
21        }
22     }
23     return min-1;
24 }
25 
26 int main() 
27 {
28     int j,x,num;
29     int a[] = {1,2,3,4,5,6,7,8,9};
30     printf("输入要查找的数\n");
31     scanf("%d",&x);
32     j = sizeof(a)/sizeof(a[0]);
33     num = func(a,j,x);
34     printf("要查找的数为a[%d]\n",num);
35     
36     return 0;
37 }

7.颜色分类

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

https://blog.csdn.net/weixin_38072112/article/details/104375297

1 #include <stdio.h>2 #include <string.h>3 4 #define N 65 6 void swap(int *a,int *b)7 {8     int temp = *a;9     *a = *b;
10     *b = temp;
11 }
12 
13 int main() 
14 {
15     int i = 0,start = 0,end = N-1;
16     int a[] = {2,1,1,0,1,0};
17     while(i<N)
18     {
19         if(a[i] == 0)
20         {
21            swap(&a[i],&a[start]);
22            start++;
23            i++;
24         }
25         else if(a[i] == 2)
26         {
27            swap(&a[i],&a[end]);
28            end--;
29         }
30         else
31         {
32            i++;
33         }
34     }
35     for(int i = 0;i<N-1;i++)
36     {
37         printf("%d ",a[i]);
38     }
39     
40     return 0;
41 }