一.冒泡排序
1基本思想: 相邻的两个数之间进行比较,按照规则进行交换。
2.实现思路:
(以升序排列为例) 第一趟比较: 先用第一个和第二个元素进行比较,将较大的交换到第二个位置上, 然后第二个和第三个进行比较,将较大的放在第三个位置上。。。 依次类推,第一趟比较结束时,最大的元素就在最后一个位置上了 然后进行第二趟比较: 先用第一个和第二个元素进行比较,将较大的交换到第二个位置上, 然后第二个和第三个进行比较,将较大的放在第三个位置上。。。 依次类推,由于第一趟比较已经将最大放在最后一个位置了 所以第二趟可以少比较一个元素,第二趟结束时, 第二大的元素就放在了倒数第二个位置上 依次类推,直到最后一趟比较完成,整个数组排序完成。 (最后一趟时,只剩下一个元素了,可以不参与比较)
3.实现动态图
4代码实现
#include <stdio.h>
int main(int argc, const char *argv[])
{
int s[10] = {23,45,65,78,90,55,33,17,96,54};
int i = 0;
int j = 0;
int temp = 0;
int flags=0;//设置这个是为了提高效率
int len = sizeof(s)/sizeof(int);
for(i = 0; i < len; i++){
printf("%d ", s[i]);
}
printf("\n");
for(j = 0; j < len-1; j++){
flags=0;
for(i = 0; i < len-1-j; i++){
if(s[i] > s[i+1]){
temp = s[i];
s[i] = s[i+1];
s[i+1] = temp;
flags=1;
}
}
if(flags==0){
break;
}
}
for(i = 0; i < len; i++){
printf("%d ", s[i]);
}
printf("\n");
return 0;
}
二.快速排序
1概念
快速排序是冒泡排序的优化,也是一种基于交换的排序方式。
时间复杂度 O(nlogn)。
2 基本思想
分而治之通过一趟排序,先将数据分成两部分,其中一部分的数据,都比另一部分的数据大(小),(每部分数据内部不要求有序)然后,对于两部分数据分别进行上述的排序操作,把没部分数据再分成两部分,依次类推,直到整个数据有序。
3实现动态图
4代码实现
#include <stdio.h>
#include <unistd.h>
int sort(int *num,int low,int high)
{
int flag=num[low];
while(low<high){
while(num[high]>flag&&low<high){
high--;
}
if(low<high){
num[low]=num[high];
}
while(num[low]<flag&&low<high){
low++;
}
if(low<high){
num[high]=num[low];
high--;
}
}
num[low]=flag;
return low;
}
int quick_sort(int *num,int low,int high)
{
if(low<high){
int ret=sort(num,low,high);
quick_sort(num,0,ret-1);
quick_sort(num,ret+1,high);
}
}
int show_num(int *num)
{
for(int i=0;i<10;i++){
printf("%d ",num[i]);
}
puts("");
}
int main(int argc, char const *argv[])
{
int num[10]={3,4,12,65,31,52,34,76,6,10};
show_num(num);
quick_sort(num,0,9);
show_num(num);
return 0;
}
三.选择排序
3.1基本思想
3.2代码实现
#include <stdio.h>
#include <stdlib.h>
void choose_sort(int *arr)
{
if (NULL == arr){
printf("传参错误\n");
exit(-1);
}
int i;
int j;
int max = 0;
int temp;
for (i = 0; i < 7; i++){
max = i;
for (j = i + 1; j < 8; j++){
if (arr[j] > arr[max]) max = j;
}
if (max != i){
temp = arr[max];
arr[max] = arr[i];
arr[i] = temp;
}
}
return;
}
int main(int argc, char const *argv[])
{
int arr[8] = {8, 12, 28, 3, 53, 22, 0, 7};
choose_sort(arr);
for (int i = 0; i < 8; i ++){
printf("%d ", arr[i]);
}
puts("");
return 0;
}