冒泡排序:
排序思路:
1.从第0个元素开始,每次用相邻的两个元素进行比较
2.一旦发现后面的一个元素小于我们前面的一个元素就交换位置
3.经过一轮冒泡排序比较之后最后一个元素就是最大值
4.排除最后一个元素,以此类推,每次比较完成后最大值都会出现在
被计较所有元素的最后一个位置,直到当前元素没有可比较的,冒泡
排序完成
冒泡排序:
3 7 4 2 6 1
冒泡
一趟冒泡排序
1.
[3 7] 4 2 6 1
因为3<7所以不用交换
3 7 4 2 6 1
2.
3 [7 4] 2 6 1
因为7>4
3 4 7 2 6 1
3.
3 4 [7 2] 6 1
因为7>2
3 4 2 7 6 1
4.
3 4 2 [7 6] 1
因为7>6
3 4 2 6 7 1
5.
3 4 2 6 [7 1]
因为7>1
3 4 2 6 1 7
二趟冒泡排序:
3 4 2 6 1 7
[3 4] 2 6 1 7
3 [4 2] 6 1 7
3 2 [4 6] 1 7
3 2 4 [6 1] 7
3 2 4 1 6 7
三趟排序冒泡排序:
3 2 4 1 6 7
[3 2] 4 1 6 7
2 [3 4] 1 6 7
2 3[4 1] 6 7
2 3 1 4 6 7
四趟冒泡排序:
[2 3] 1 4 6 7
2 [3 1] 4 6 7
2 1 3 4 6 7
五趟冒泡排序
1 2 3 4 6 7
作用:把当前待比较的数组中的最大值放到最后面
#include <stdio.h>
#include <stdlib.h>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
void bubble(int arr[],int n)//函数里面按传递我们的数组和数组长度
{
int i;
int temp;
for(i=0;i<n-1;i++)
{
//如果数组中前面的一个原素大于数组中后面的一个元素,就进行交换
if(arr[i]>arr[i+1])
{
temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
}
}
}
// void bubbleSort(int arr[],int n)
// {
// bubble(arr,n);//经过冒泡排序之后,最大的树放到了最后面,此时只需要对数组的前n-1个数排序就可以了
// bubble(arr,n-1);
// bubble(arr,n-2);
// .....
// bubblr(arr,1);
// }
void bubbleSort(int arr[],int n)
{
int i;
for(i=n;i>=1;i--)
{
bubble(arr,i);
}
}
int main(int argc, char *argv[]) {
int arr[] = {3,2,4,1,6,7};
int i;
bubbleSort(arr,6);
for(i=0;i<6;i++)
{
printf("%d\n",arr[i]);
}
return 0;
}
#########################################################################################
#include <stdio.h>
#include <stdlib.h>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
int main(int argc, char *argv[]) {
int a[6] = {3,2,4,1,6,7};//6个数的无序数列
int i,j,t;
for(i=0;i<6-1;i++)//6个数的数列总共需要扫描6-1次
{
for(j=0;j<6-i-1;j++)//每一趟扫描到a[n-i-2]与a[n-1-1]比较为止结束
{
if(a[j]>a[j+1])//前面一位数比后一位数大的话,就交换两个数的位置
{
t = a[j+1];
a[j+1]=a[j];
a[j]=t;
}
}
}
for(i=0;i<6;i++)
{
printf("%d ",a[i]);
}
return 0;
}
#######################################################################################
#include <stdio.h>
#include <stdlib.h>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
void bubbleSort(int arr[],int n)
{
int i,j,temp;
for(i=0;i<n-1;i++)//控制比较的次数
{
for(j=0;j<n-1-i;j++)//控制每轮比较的次数
{
if(arr[j]>arr[j+1])//交换两个元素的条件
{
temp = arr[j];
arr[j]= arr[j+1];
arr[j+1] = temp;
}
}
}
}
void pirnt(int arr[],int n)
{
int i;
for(i=0;i<n;i++)
{
printf("%d\n",arr[i]);
}
}
int main(int argc, char *argv[]) {
int arr[6] = {3,4,2,6,1,7};
bubbleSort(arr,6);
pirnt(arr,6);
return 0;
}
选择排序:
找出最大值与最后一个元素交换
3 7 4 2 6 1
1.
7和1进行交换
[3 1 4 2 6 ] 7
2.
6已经是数组当中的最大值,且在待排序数组的最后一个位置
[3 1 4 2] 6 7
3.
4和2进行交换
[3 1 2] 4 6 7
4.
3和2进行交换
[2 1] 3 4 6 7
5.
2 和 1进行交换
1 2 3 4 6 7
#include <stdio.h>
#include <stdlib.h>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
// int findMax(int arr[],int n)//其实我们找的不是最大值,而是最大值的下标
// {
// int max = arr[0];
// int i;
// for(i=0;i<n;i++)
// {
// if(arr[i]>max)
// {
// max = arr[i];
// }
// }
// return max;
// }
int findMaxPos(int arr[],int n)
{
int max = arr[0];
int pos = 0;
int i;
for(i=0;i<n;i++)
{
if(arr[i]>max)
{
max = arr[i];
pos = i;
}
}
return pos;
}
void selectionSort(int arr[],int n)
{
while(n>1)
{
int pos = findMaxPos(arr,n);
int temp = arr[pos];
arr[pos] = arr[n-1];
arr[n-1] = temp;
n--;
}
}
int main(int argc, char *argv[]) {
int arr[] = {3,4,2,6,1,7};
selectionSort(arr,6);
int i;
for(i=0;i<6;i++)
{
prinf("%d\n",arr[i]);
}
return 0;
}
插入排序:
3 6 7 4 2 1 5
分为两个部分,一个部分已经排好序,一个部分还没有排好序
[3 6 7]4 2 1 5
从4开始插入到我们前面已经排好序的数组中
写代码:
arr 0 1 2 3 i
3 6 7 4 key
while(arr[i-1]>key)
{
=>arr[i] = arr[i-1];
i--;
}
arr[i] = key
3 6 7 4 2 1 5
3 6 7 这三个数字已经排好序
对4进行操作
从后往前进行比较
4和7比,4小于7
3 6 4 7 2 1 5先不管
对6和4,6大于4
3 4 6 7
对于4和3来说,3小于4,因此他俩不需要交换位置
3 4 6 7 2 1 5
下面对2进行操作
[3 4 6 7] 2 1 5
对于7和2来说,7大于2
3 4 6 2 7 1 5先不管他俩
下面6和2
#include <stdio.h>
#include <stdlib.h>
void insert(int arr[],int n)
{
int key = arr[n];
int i = n;
while(arr[i-1]>key)
{
arr[i] = arr[i-1];
i--;
if(i==0)
{
break;
}
}
arr[i] = key;
}
void insertionSort(int arr[],int n)
{
int i;
for(i=1;i<n;i++)
{
insert(arr,i);
}
}
int main(int argc, char *argv[]) {
int arr[] = {3,6,7,4,2,1,5};
int i;
insertionSort(arr,7);
for(i=0;i<7;i++)
{
printf("%d\n",arr[i]);
}
return 0;
}