欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-04-08 17:50:40
算法是解决一类问题的方法排序算法 根据元素大小关系排序 从小到大 从大到小冒泡 选择 插入 快排希尔排序 归并排序 堆排序 冒泡排序 从头到尾比较 每一轮将最大的数沉底 或者最小数字上浮 选择排序 1.找到最小/大的数字放到最前面 2.除过第一个数字以外,找到最小/大的数字与第二个元素对换 每一轮只 ......

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

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

选择排序 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