排序算法
插入排序
直接插入排序
基本思想:
我们将一个待排序序列分为有序区和无序区（一般开始的时候将第一个元素作为有序区，剩下的元素作为无序区），每次将无序区的第一个元素作为待插入记录，按大小插入到前面已经排好的有序区中的适当位置，直到记录全部插入完成为止。(如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面)
** C++实现 **
void insert_sort_1(int a[],int n)//对n个元素从小到大排序
{
int i,j;
int temp;
for(i=1;i<n;i++)
{
temp = a[i];//待插入元素
j = i-1;
while(temp<a[j] && j)
{
a[j+1] = a[j];//将大的往后挪
j--;//顺利的话可以减到-1，要么就是减到可以插入的位置的前一个位置
//所以后面的j需要加1
}
a[j+1]=temp;
}
}** C++实现_2 **
#include<iostream>
using namespace std;
void insert_sort_2(int a[],int n)//n个数,排的实际上是下标为1到n-1的元素,a[0]是监视哨
{
int i,j;
//初始状态下a[1]为初始有序区
//a[2]到a[n-1]为无序区
for(i=2;i<n;i++)
{
a[0] = a[i];//设置监视哨
j = i-1;
while(a[0]<a[j])//将有序区中大于监视哨的元素往后挪，没有就不动
{
a[j+1] = a[j];
j--;//如果顺利可以减到0下标
}
a[j+1] = a[0];
}
}
int main()
{
int temp[11]={0,10,9,8,7,6,5,4,3,2,1};//真正用于排序的只有10个数
insert_sort_2(temp,11);
for(int i=1;i<11;i++)
{
cout<<temp[i]<<endl;
}
return 0;
} 直接选择排序
冒泡排序
基本思想:
我们把待排序元素序列竖直放置，每趟对相邻的元素进行两两比较，顺序相反则进行交换，每趟会将最小或最大的元素“浮”到元素序列的顶端，最终元素序列达到有序
** C++实现 **
#include<iostream>
using namespace std;
void bubble_sort(int array[],int n)//对n个数从小到大排序，注意数组下标从0开始
{
int i,j;
int temp;
for(i=0;i<n-1;i++)//进行n-1趟比较
{
for(j=0;j<n-1-i;j++)//每趟进行n-1-i次比较
{
if(array[j+1]<array[j])
{
temp = array[j+1];
array[j+1] = array[j];
array[j] = temp;
}
}
}
}
int main()
{
int a[10] = {10,9,7,8,6,5,4,2,3,1};
bubble_sort(a,10);
for(int i=0;i<10;i++)
{
cout<<a[i]<<" ";
}
return 0;
} 快速排序
快速排序是分治思想在排序算法上的应用，从本质上来讲快速排序应该是在冒泡排序基础上的递归分治法。
算法步骤:
- 从待排数列中选出一个元素作为基准，一般选第一个元素
- 重新排序待排数列，所有元素比基准小的摆放在基准前面，所有元素比基准大的摆放在基准后面（相同的数可以放在任意一边）。在这个分区退出后，该基准就处于中间位置。（这个即为分区操作(partion)）。
- 递归地把小于基准元素的子数列和大于基准元素的子数列进行排序。
** C实现 **
#include<stdio.h>
int a[101],n;
void quick_sort(int left, int right)
{
int i,j,temp;
int t;
if(left > right)
{
return ;
}
temp = a[left];//基准数
i = left;
j = right;
while(i != j)
{
//顺序很重要，先从右往左找
while( a[j] >= temp && i<j)
{
j--;
}
//再从左边往右找
while( a[j] <= temp && i<j)
{
i++;
}
//交换两个数在数组中的位置
if(i<j)//两个哨兵没有相遇
{
t = a[i];
a[i] = a[j];
a[j] = t;
}
}
//最终将基准数归位,
a[left] = a[i];
a[i] = temp;//归位
quick_sort(left,i-1);//继续处理左边的数
quick_sort(i+1,right);//继续处理右边的数
return ;
}
int main()
{
int i,j;
scanf("%d",&n);
for(i=1; i<=n; i++)//下表从1开始
scanf("%d",&a[i]);
quick_sort(1,n);//sort
for(j=1; j<=n; j++)
printf("%d ",a[j]);
return 0;
} 参考:
