C++学习（三十八）（C语言部分）之 排序（冒泡 选择 插入 快排）

算法是解决一类问题的方法
排序算法 根据元素大小关系排序 从小到大 从大到小
冒泡 选择 插入 快排
希尔排序 归并排序 堆排序

冒泡排序 从头到尾比较 每一轮将最大的数沉底 或者最小数字上浮

选择排序 1.找到最小/大的数字放到最前面 2.除过第一个数字以外，找到最小/大的数字与第二个元素对换 每一轮只交换一次数字

插入排序
假如 1 2 5 9 0
（1）现在1是有序的 选择5 和1比较，大了放1前面小了放1后面
后面的元素一个个插入到前面的队列中 插入保证有序
最后插入完成之后 这个元素的序列也是有序的
快速排序

一般排序 时间复杂度小 空间复杂度会较高
空间复杂度小 时间复杂度会高

时间 空间 用时间换空间 要么用空间换时间
--> 要么用时间换内存 要么用内存换时间

 

测试代码笔记如下：

  1 #include<stdio.h>
  2 
  3 //拆分出一个函数实现  1.排序的数组 2.数组中的元素格式确定排序次数---->参数
  4 
  5 //冒泡排序
  6 void bullet_sort(int*arr,int len)  //或者 int*arr  是一样的  int len 是数组大小
  7 {
  8     int temp;
  9     printf("冒泡排序过程：\n");
 10     for (int i = 0; i < len - 1; ++i)  //循环比较次数
 11     {
 12         //for (int j = 0; j < len - 1; ++j)  //从头到尾比较一轮
 13         for (int j = 0; j < len - 1-i; ++j)  //代码优化 从头到尾比较一轮 每一轮都要少比较一个
 14         {
 15             if (arr[j]>arr[j + 1])  //发现两个位置不对的与元素
 16             {
 17                 //交换两个元素的位置
 18                 temp = arr[j];
 19                 arr[j] = arr[j + 1];
 20                 arr[j + 1] = temp;
 21             }
 22         }
 23         //测试代码
 24         for (int j = 0; j < len; ++j)
 25         {
 26             printf("%d\t", arr[j]);
 27         }
 28         printf("\n\n");
 29     }
 30 }
 31 
 32 //选择排序
 33 void select_sort(int arr[], int len)
 34 {
 35     int k,temp;
 36     printf("选择排序过程：\n");
 37     for (int i = 0; i < len-1; ++i)  //先出arr[i]这个位置的元素
 38     {
 39         k = i;  //保存这个位置的下标 作为初始条件
 40         for (int j = i + 1; j<len;++j)
 41         {
 42             if (arr[k]>arr[j])
 43             {
 44                 k = j;  //arr[j]更小 用k保存位置
 45             }
 46         }
 47         //找完之后 arr[i]  arr[k]最小 进行交换
 48         temp = arr[i];
 49         arr[i] = arr[k];
 50         arr[k] = temp;
 51         //测试代码
 52         for (int j = 0; j < len; ++j)
 53         {
 54             printf("%d\t", arr[j]);
 55         }
 56         printf("\n\n");
 57     }
 58 }
 59 
 60 //插入排序
 61 void insert_sort(int arr[],int len)
 62 {
 63     int temp;
 64     printf("插入排序过程：\n");
 65     for (int i = 1; i < len; ++i)  //从第二个人开始插入
 66     {
 67         //先找合适的位置
 68         for (int j = 0; j < i; ++j)  //j<i是因为要比较i前面的元素
 69         {
 70             if (arr[j]>arr[i])  //找比arr[i]要大的第一个元素
 71             {    //插入
 72                 //将arr[i] 插入到arr[j]的位置
 73                 temp = arr[i];  //保留要插入的数字
 74                 for (int k = i - 1; k >= j; --k)
 75                 {
 76                     arr[k + 1] = arr[k];//往后移
 77                 }
 78                 arr[j] = temp;//插入元素
 79                 break;  //退出循环 不要再比较
 80             }
 81         }
 82         //插入完成  进行下一轮循环
 83         //测试代码
 84         for (int j = 0; j < len; ++j)
 85         {
 86         printf("%d\t", arr[j]);
 87         }
 88         printf("\n\n");
 89     }
 90 }
 91 
 92 //快速排序
 93 int part(int arr[], int begin, int end)//将一个数组分成两个部分 有一个arr[k]  比arr[k]小的元素 全部在arr[k]左边  比arr[k]大的元素全部在arr[k]右边
 94 //返回这个k的值
 95 {
 96     //1.选中arr[begin]作数字
 97     int i = begin, j = end, temp;
 98     while (i < j)
 99     {
100         //从右边找到一个比arrr[begin]小的元素
101         while (i<j&&arr[j]>arr[begin]) --j;//找一个比arr[begin]要小的元素 
102         //从左边找到一个比arrr[begin]大的元素
103         while (i<j&&arr[i] <= arr[begin]) ++i;
104         temp = arr[i]; 
105         arr[i] = arr[j]; 
106         arr[j] = temp;//交换元素
107     }
108     //退出来的时候  i==j的 并且arr[i]这个位置 就是要找的k
109     //arr[begin] 和arr[i]交换
110     temp = arr[begin]; 
111     arr[begin] = arr[i]; 
112     arr[i] = temp;
113     return i;
114 }
115 void quick_sort(int arr[], int begin, int end)
116 {
117     if (begin >= end) return;
118     //begin必须小于end才需要排序
119 
120     //1.分成两个部分
121     int k = part(arr, begin, end);//分成两个部分
122 
123     //arr[k]左边的元素全部小于arr[k]   arr[k]右边元素全部大于arr[k]
124     //2.排序左边
125     quick_sort(arr, begin, k - 1);//k的位置不参与排序 所以是k-1
126     //3.排序右边
127     quick_sort(arr, k + 1, end);
128 }
129 
130 int main()
131 {
132 //定义乱序数组并原样输出
133     int arr[10] = {1,5,2,9,0,6,3,8,7,4};    //乱序数组
134     printf("排序前输出：");
135     for (int i = 0; i < 10; ++i)  //打印出数组中的元素
136     {
137         printf("%d\t", arr[i]);
138     }
139     printf("\n\n");
140 
141 //冒泡排序 
142 // bullet_sort(arr, 10);  //调用函数 参数值是数组名以及数组大小
143 
144 //选择排序
145 //    select_sort(arr, 10);
146 
147 //快速排序
148     quick_sort(arr, 0, 9);
149 
150     //int temp;
151     //for (int i = 0; i < 9; ++i)  //排序九轮
152     //{
153     //    for (int j = 0; j < 9; ++j)  //从头到尾比较
154     //    {
155     //        if (arr[j] > arr[j + 1])  //比较 >是从小到大 <是从大到小  j+1<10 -----> j<9
156     //        {
157     //            //交换两个元素的位置
158     //            temp = arr[j];
159     //            arr[j] = arr[j + 1];
160     //            arr[j + 1] = temp;
161     //        }
162     //    }
163     //}
164     
165     //输出排序
166     printf("排序后输出：");
167     for (int i = 0; i < 10; ++i)
168     {
169         printf("%d\t", arr[i]);
170     }
171     getchar();
172     return 0;
173 }

2019-04-02  17:35:13