冒泡排序是最简单的排序方法:原理是:从左到右,相邻元素进行比较。每次比较一轮,就会找到序列中最大的一个或最小的一个。这个数就会从序列的最右边冒出来。(注意每一轮都是从a[0]开始比较的)
以从小到大排序为例,第一轮比较后,所有数中最大的那个数就会浮到最右边;第二轮比较后,所有数中第二大的那个数就会浮到倒数第二个位置……就这样一轮一轮地比较,最后实现从小到大排序。
2、鸡尾酒排序
鸡尾酒排序又称双向冒泡排序、鸡尾酒搅拌排序、搅拌排序、涟漪排序、来回排序或快乐小时排序, 是冒泡排序的一种变形。该算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。
原理:数组中的数字本是无规律的排放,先找到最小的数字,把他放到第一位,然后找到最大的数字放到最后一位。然后再找到第二小的数字放到第二位,再找到第二大的数字放到倒数第二位。以此类推,直到完成排序。
3、选择排序
思路是设有10个元素a[1]-a[10],将a[1]与a[2]-a[10]比较,若a[1]比a[2]-a[10]都小,则不进行交换。若a[2]-a[10]中有一个以上比a[1]小,则将其中最大的一个与a[1]交换,此时a[1]就存放了10个数中最小的一个。同理,第二轮拿a[2]与a[3]-a[10]比较,a[2]存放a[2]-a[10]中最小的数,以此类推。
4、插入排序
插入排序是在一个已经有序的小序列的基础上,一次插入一个元素*
一般来说,插入排序都采用in-place在数组上实现。
具体算法描述如下:
⒈ 从第一个元素开始,该元素可以认为已经被排序
⒉ 取出下一个元素,在已经排序的元素序列中从后向前扫描
⒊ 如果该元素(已排序)大于新元素,将该元素移到下一位置
⒋ 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
⒌ 将新元素插入到下一位置中
⒍ 重复步骤2~5
常用的c语言排序算法主要有三种即冒泡法排序、选择法排序、插入法排序。
一、冒泡排序冒泡排序:
是从第一个数开始,依次往后比较,在满足判断条件下进行交换。代码实现(以降序排序为例)
#include<stdio.h>
int main()
{
int array[10] = { 6,9,7,8,5,3,4,0,1,2 }
int temp
for (int i = 0i <10i++)
{//循环次数
for (int j = 0j <10 - i-1j++)
{
if (array[j] <array[j+1])
{//前面一个数比后面的数大时发生交换 temp = array[j]
array[j] = array[j+1]
array[j + 1] = temp
}
}
} //打印数组 for (int i = 0i <10i++) printf("%2d", array[i])return 0}}
二、选择排序以升序排序为例:
就是在指定下标的数组元素往后(指定下标的元素往往是从第一个元素开始,然后依次往后),找出除指定下标元素外的值与指定元素进行对比,满足条件就进行交换。与冒泡排序的区别可以理解为冒泡排序是相邻的两个值对比,而选择排序是遍历数组,找出数组元素与指定的数组元素进行对比。(以升序为例)
#include<stdio.h>
int main()
{
int array[10] = { 6,9,7,8,5,3,4,0,1,2 }
int temp, index
for (int i = 0i <9i++) {
index = i
for (int j = ij <10j++)
{
if (array[j] <array[index])
index = j
}
if(i != index)
{
temp = array[i]
array[i] = array[index]
array[index] = temp
}
for(int i=0i<10:i++)
printf("%2d"array[i])
return 0;
}
三、快速排序
是通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
void QuickSort(int* arr, int size)
{
int temp, i, j
for(i = 1i <sizei++)
for(j=ij>0j--)
{
if(arr[j] <arr[j-1])
{
temp = arr[j]
arr[j]=arr[j-1]
arr[j-1]=temp
}
}
}
选择排序
#include <iostream>using namespace std
void select_sort(int arr[], int num)
void output_array(int arr[], int num)
int main()
{
int a[10]
for(int i=0 i<10 i++)
{
cin>>a[i]
}
select_sort(a,10)
output_array(a,10)
return 0
}
void select_sort(int array[],int n) //形参array是数组名
{
int i,j,k,t
for(i=0 i<n-1 i++)
{
k=i //先设第i个就为最小
for(j=i+1 j<n j++)
if(array[j]<array[k])
k=j //通过循环,得到k为最小
t=array[k] //交换a[i]和a[k]
array[k]=array[i]
array[i]=t
}
return
}
void output_array(int arr[], int num)
{
int i
for(i=0 i<num i++)
{
cout<<arr[i]
cout<<endl
}
return
}
2.冒泡排序
#include<stdio.h>int main()
{
int i,j,a[10],t
for(i=0i<10i++)
scanf("%d",&a[i])
for(i=0i<10i++)
for(j=i+1j<10j++)
if(a[i]>a[j])
{
t=a[j]
a[j]=a[i]
a[i]=t
}
for(i=0i<10i++)
printf("%d ",a[i])
return 0
}
3.堆排序
#include<iostream>using namespace std
void paidui(int a[20],int i,int m)
{
int k,t
t=a[i]
k=2*i+1
while (k<m)
{
if ((k<m-1)&&(a[k]<a[k+1]))
k++
if (t<a[k])
{
a[i]=a[k]
i=k
k=2*i+1
}
else break
}
a[i]=t
}
void duipai(int a[20], int n)
{
int i,k
for (i=n/2-1i>=0i--)
paidui(a,i,n)
for (i=n-1 i>=1 i--)
{
k=a[0]
a[0]=a[i]
a[i]=k
paidui(a,0,i)
}}
int main()
{
int a[10],i
for(i=0i<10i++)
cin>>a[i]
duipai(a,10)
for(i=0i<10i++)
cout<<a[i]<<endl
}
4.快速排序
#include<iostream>using namespace std
void Quicksort(int a[],int low,int high)
{
if(low>=high)
{
return
}
int first=low
int last=high
int key=a[first]
while(first<last)
{
while(first<last&&a[last]>=key)
--last
a[first]=a[last]
while(first<last&&a[first]<=key)
++first
a[last]=a[first]
}
a[first]=key
Quicksort(a,low,first-1)
Quicksort(a,last+1,high)
}
int main()
{
int i,a[100],x,n=0
while(cin>>x)
{
a[n]=x
n++
}
n--
Quicksort(a,0,n)
for(i=0i<=ni++)
cout<<a[i]<<" "
cout<<endl
return 0
}
5. 基数排序
#include <stdio.h>#include <stdlib.h>
int main(){
int data[10]={73,22,93,43,55,14,82,65,39,81} //对十个数进行排序
int temp[10][10]={0} //构造一个临时二维数组,其值为0
int order[10]={0} //构造一维数组,其值为0
int i,j,k,n,lsd
k=0n=1
for (i=0i<10i++) printf("%d ",data[i]) //在排序前,对这10个数打印一遍
putchar('\n')
while (n<=10){
for (i=0i<10i++){
lsd=((data[i]/n)%10) //lsd先对个位取余,然后再对十位取余,注意循环
temp[lsd][order[lsd]]=data[i] //temp[3][0]=73,temp[2][0]=22,temp[3][1]=93,temp[3][2]=43,⋯⋯
order[lsd]++ //需要区分的是lsd和order[lsd],这两个不是一样的概念嗷
}
printf("\n重新排列: ")
for (i=0i<10i++){
if(order[i]!=0)
for (j=0j<order[i]j++){
data[k]=temp[i][j]
printf("%d ",data[k])
k++
}
order[i]=0
}
n*=10 //第二次用十位
k=0
}
putchar('\n')
printf("\n排序后: ")
for (i=0i<10i++) printf("%d ",data[i])
return 0
}
6.希尔排序
#include<iostream>using namespace std
void shell_sort(int a[],int n)
int main()
{
int n,a[10000]
cin>>n
for(int y=0y<ny++)
cin>>a[y]
shell_sort(a, n)
for(int i=0 i<n i++)
cout<<a[i]<<" "
cout<<endl
}
void shell_sort(int a[], int n)
{
int gap,k,temp//定义增量;
for(gap = 3 gap >0 gap--)//设置初始增量,递减;
{
for(int i=0 i<gap i++)//按增量分组;
{
for(int j = i+gap j<n j=j+gap)//每组分别比较大小;
{
if(a[j]<a[j-gap])
{
temp = a[j]
k = j-gap
while(k>=0&&a[k]>temp)
{
a[k+gap] = a[k]
k = k-gap
}
a[k+gap] = temp
}
}
}
}
}
7.归并排序
#include<iostream>using namespace std
void MergeSort(int p[],int s,int m,int t)
{
int q[100] //q[100]用来存放排好的序列
int i=s
int j=m+1
int k=s
while(i<=m&&j<=t)
{
if(p[i]<=p[j])
q[k++]=p[i++]
else
q[k++]=p[j++]
}
if(i<=m)
while(i<=m)
q[k++]=p[i++]
else while(j<=t)
q[k++]=p[j++]
for(int n=sn<=tn++)
p[n]=q[n]
}
void Merge(int p[],int s,int t)
{
if(s<t)
{
int m=(s+t)/2 //将数组分成两半
Merge(p,s,m)//递归拆分左数组
Merge(p,m+1,t)//递归拆分右数组
MergeSort(p,s,m,t)//合并数组
}
}
int main()
{
int n
int p[100]
cin>>n
for(int i=0 i<n i++)
cin>>p[i]
Merge(p,0,n-1)
for(int j=0j<nj++)
cout<<p[j]<<" "
cout<<endl
return 0
}
排序方法基本就这些,还有双向冒泡这种拓展的排序方法,还有直接排序如桶排序