ZEROCATH

身无长物江湖远,胸有沟壑天地宽

0%

排序算法

初级排序算法

选择排序

  • Selection

    描述

    先找到数组中最小的值,与第一个元素交换位置,再次在剩下的元素中找到最小的元素与第二个元素交换位置,以此类推直至将整个数组排序。即不断选择剩余数组中的最小值

复杂度分析

  • 需要N^2/2次比较和N次交换
  • 运行时间和输入顺序无关
  • 数据移动次数最小

实现

  • C
1
2
3
4
5
6
7
8
9
10
11
12
13
void Selection(int *a[],int size)
{
for(int i=0;i<size;i++)
{
int minIndex=i;
for(int j=i+1;j<size;j++)
if(a[j]<a[minIndex])
minIndex=j;
int temp = a[i];
*a[i]=a[minIndex];
*a[minIndex]=temp;
}
}

插入排序

描述

按下标从左到右访问各元素,确保每次访问元素的左侧是有序的。

复杂度

  • 需要的时间与元素初始顺序有关
  • 比较次数:N-1~N^2/2
  • 交换次数:0~N^2/2
  • 时间复杂度O(n^2)

实现

  • C
1
2
3
4
5
6
7
8
9
10
11
12
void Insertion(int a[],int n){
for(int i=1;i<n;i++)
{
int j=i;
for(j;a[j]>a[j-1];j--)
{
int temp=a[j];
a[j]=a[j-1];
a[j-1]=temp;
}
}
}

希尔排序

Shell Sort,基于插入排序的快速的排序算法

描述

将数组分组,将每个子数组排序,逐步缩小子数组中所含元素的个数至1,则排序结束

实现

  • C
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    void ShellSort(int a[],int n)
    {
    for(int gap=n/2;gap>0;gap/=2)
    {
    //对每个子数组做插入排序
    for(int i=gap;i<n;i++)
    {
    int temp=arr[i];
    int j=i;
    for(j;j>=gap&&arr[j-gap]>temp;j-=gap)
    arr[j]=arr[j-gap];
    }
    }
    }
  • Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Shell
{
public static void sort(Comparable[] a)
{
int N =a.length;
int h=1;
while(h<N/3)
h=3*h+1;
while(h>=1)
{
for(int i=h;i<N;i++)
{
for(int j=i;j>=h&&a[j]>a[j-h];j-=h)
exch(a,j,j-h);//交换,实现略
}
h=h/3;
}
}
}

归并排序

Merge Sort

思路

采用分治思想,先分后治

实现

  • C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
void merge(int a[],int s,int m,int e)
{
//将a[s:m],a[m+1:e]两有序子列归并为有序
int i,j,k;
//申请空间存放有序数组
int *b=(int*)malloc(sizeof(int)*(e-s+1));
for(i=m+1,k=0,j=s;j<=m&&i<=e;k++)
{
if(a[j]<=a[i])
b[k]=a[j++];
else
b[k]=a[i++];
}//将两各=个有序数组归并
while(j<=m)
b[k++]=a[j++];
while(i<=e)
b[k++]=a[i++];
for(i=s,k=0;i<=e;i++,k++)
a[i]=b[k];
free(b);
}
void msort(int a[],int s,int e)
{
//将a[s:e]进行归并排序
if(s<e)
{
//1分为2
int m=(s+e)/2;
msort(a,s,m);
msort(a,m+1,e);//递归调用
merge(a,s,m,e);
}
}
void mergeSort(int a[],int length)
{
msort(a,0,length-1);
}

快速排序

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void exch(int a[],int a,int b)
{
int temp=a[a];
a[a]=a[b];
a[b]=temp;
}
void partition(int a[],int lo,int hi)
{
int v=a[lo];
int i=lo,j=hi+1;
while(1)
{
while(a[++i]<=v)
if(i==hi) break;
while(v<=a[--j])
if(j==lo) break;
if(i>=j) break;
exch(a,i,j)
}
exch(a,lo,j);
return j;
}

void quickSort(int a[],int lo,int hi)
{
if(hi<=lo) return;
int j=partition(a,lo,hi);//a[lo:j-1]不大于a[j],a[j+1:hi]不小于a[j]
quickSort(a,lo,j-1);
quickSort(a,j+1,hi);
}