各种排序原理及其C语言实现

包含冒泡,选择,插入,shell,快速,合并(归并)排序的原理及其C语言实现,其中归并排序又分为递归和迭代排序算法。代码已通过验证。

排序的方法，按照排序过程中结果序列生成的过程可以分为交换法、选择法和插入法。

冒泡排序：

基本思想：首先制定排序规则，例如按照数据由大到小或由小到大的顺序，然后依稀两两比较待排序的数据，若不符合排序规则，则进行交换。这样比较一遍之后，便有一个数据元素确定位置，然后依次比较下去，直到全部元素排列有序为止。

选择排序：

基本思想：首先制定排序规则（例如按照从小到大排序原则），排序过程中首先在未排序序列中找到最小值，放在排序序列起始位置，随后，逐趟从余下未排序的数值中逐次寻找最小值，直到整个序列有序为止。

插入排序：

基本思想：当插入第i个元素的时候，前面i-1个元素已经排列好了，这时只需要用第i个的关键字从最后开始与其他的进行比较，找到合适的位置，将后面的对象依次后移，然后将新的对象插入。

直接插入排序最大的优点就是具有合理性，也就是说，如果初始序列的情况较好，那么排序所需的移动比较次数就少，如果初始序列情况差，那么所需要的移动比较次数就多，因此直接插入排序适合那些基本上已经按顺序排列的序列。

Shell 排序：（缩小增量排序：diminishing increments）

基本思想：设待排序的对象序列有n个元素，首先取一个整数gap<n作为间隔，将全部元素分为gap个子序列，所有距离为gap的元素属于同一个子序列，在每一个子序列中分别采用直接插入法，然后缩小gap，直到gap=1，将所有对象放到同一个序列再排一次为止，其排序速度可以在一定程度上有所提高。

Gap的取法：最初Shell认为gap=n/2,然后依次取gap=gap/2，后来Knuth提出gap=gap/3+1.还有人提出都去奇数比较好，总之，不同的研究者提出了不同的算法，但无论哪一种提法都没有得到证明。

快速排序：

快速排序是冒泡排序的一种改进，由图灵奖获奖者、英国计算机系统大师霍尔（C.A.R Hoare）在1962年提出并演化而来的。

基本思想：通过一趟数据比较和交换，将要排序的数据分成前后两部分，其中一部分的数据比另外一部分的数据都要小，然后，再按照这种方法对分开的两部分数据分别进行一次快速排序，依次执行下去，直到整个序列有序为止。

例如，对无序序列a[n] {a0,a1,...an 1}，使用快速排序的过程为：首先，任选一个数据（通常选第一个元素数据a0）作为关键数据。然后，将所有比它小的元素都交换到它前面，所有比它大的元素都交换到它后面，执行这样一次比较和交换的过程成为一趟快速排序。一趟快速排序的算法描述如下：

1） 设置两个变量low和high，排序初始时设置初始值为：low=0，high=n-1；

2） 取第一个元素a0作为关键数据，赋值给临时变量temp,即令temp=a0;

3） 从high开始逐渐向序列前面搜索，即执行j—操作，依次与temp比较，直到找到第一个小于temp的

元素位置，然后将找到的元素与temp交换；

4） 从low开始向序列后面搜索，即执行i++操作，依次与temp比较，直到找到第一个大于temp的元素，

然后将找到的元素与temp交换；

5） 重复上述3）、4）步，直到i=j。

包含冒泡,选择,插入,shell,快速,合并(归并)排序的原理及其C语言实现,其中归并排序又分为递归和迭代排序算法。代码已通过验证。

合并排序：

合并排序又叫归并排序，合并排序的主要目的是将两个或多个有序的数组或链表等有序表合成一个新的有序表。最简单的合并是将两个有序数组合并成一个有序数组。典型的合并算法是2-路合并排序，即按照排序规则将两个位置相邻的有序表合并为一个有序表。

1. 两个数组合并排序

将两个有序数组Array1和Array2进行排序放到另一个数组ArrayMerge的基本思想为：首先，在Array和Array2数组中各取第一个元素进行比较，将较小的元素放入数组ArrayMerge；然后，取较小元素所在数组的下一个元素与另一数组中上次比较后较大的元素比较，重复上述比较过程，直到某个数组先排序完；最后，将另一个数组中剩余元素连接到数组ArrayMerge中。

2. 合并排序算法

合并排序算法最常用的是2-路合并算法。使用2-路合并排序算法，可以将无序序列排列成有序序列。通常，可以采用递归形式的2-路合并排序方法。其基本思想是将含有n个元素的待排序序列分为n个子序列，然后，两两进行合并，得到n/2或n/2+1个含有2个元素的子序列，将这些子序列再两两合并，直到生成一个长度为n的有序序列为止。

例如，有序列{ 85, 279, 948, 521, 616, 888, 0}，将上述序列按照从小到大排列，使用合并排序算法的示意图如下图所示：Recursion

2-路合并排序过程

//从分治策略的机制入手，容易消除归并排序算法中的递归，事实上，递归算法MergeSort的递归过程只是将待排序列集合一分为二，直到待排序列集合只剩下一个元素为止，然后不断合并两个排好序的数组段。按此机制，可以首先 将数组a中相邻元素两两配对。用合并算法将它们排序，构成n/2组长度为2的排好序的子数组段，然后再将它们 排序成长度为4的排好序的子数组段，如此继续下去，直至整个数组排好序。这就是自然合并排序的思想。对于n元数组已排好顺序情况下，自然排序算法不执行合并，而递归算法MergeSort需执行[logn]次合并。

Iteration

包含冒泡,选择,插入,shell,快速,合并(归并)排序的原理及其C语言实现,其中归并排序又分为递归和迭代排序算法。代码已通过验证。

1) 冒泡排序

#include <stdio.h>

#define N 5

void BubbleSort(int a[], int n)

{

int i=0,j=0,temp=0;

printf("Start processing function BubbleSort()\n\n"); for(i=0;i<n-1;i++)

{

for (j=0;j<n-1-i;j++)

{

if (a[j]>a[j+1])

{

temp = a[j];

a[j] = a[j+1];

a[j+1] = temp;

}

}

}

}

void main()

{

int array[N],i;

printf("Please enter %d integers:\n",N);

for (i=0;i<N;i++)

{

scanf("%d",&array[i]);

}

printf("\n");

BubbleSort(array,N);

printf("The sorted array is:\n");

for(i=0;i<N;i++)

{

printf("%-5d",array[i]);

}

printf("\n");

}

包含冒泡,选择,插入,shell,快速,合并(归并)排序的原理及其C语言实现,其中归并排序又分为递归和迭代排序算法。代码已通过验证。

2) 选择排序

#include <stdio.h>

#define N 5

void SelectSort(int a[], int n)

{

int i=0, j=0, min=0, temp=0;

printf("Start processing function SelectSort()\n\n"); for(i=0;i<n-1;i++)

{

min = i;

for (j=i+1;j<n;j++)

{

if (a[min]>a[j])

{

min = j;

}

}

if (min!=i)

{

temp = a[min];

a[min] = a[i];

a[i] = temp;

}

}

}

void main()

{

int array[N],i;

printf("Please enter %d integers:\n",N);

for (i=0;i<N;i++)

{

scanf("%d",&array[i]);

}

printf("\n");

SelectSort(array,N);

printf("The sorted array is:\n");

for(i=0;i<N;i++)

{

printf("%-5d",array[i]);

}

printf("\n");

}

包含冒泡,选择,插入,shell,快速,合并(归并)排序的原理及其C语言实现,其中归并排序又分为递归和迭代排序算法。代码已通过验证。

#include <stdio.h>

#define N 5

void InsertSort(int a[], int n)

{

int i=0,j=0,temp=0;

printf("Start processing function InsertSort()\n\n"); for(i=1;i<n;i++)

{

temp = a[i];

for (j=i-1;j>=0;j--)

{

if (a[j]>temp)

{

a[j+1] = a[j];

//a[j] = temp;

}

else

{

break;

}

}

a[j+1] = temp; // 任选其一

}

}

void main()

{

int array[N],i;

printf("Please enter %d integers:\n",N);

for (i=0;i<N;i++)

{

scanf("%d",&array[i]);

}

printf("\n");

InsertSort(array,N);

printf("The sorted array is:\n");

for(i=0;i<N;i++)

{

printf("%-5d",array[i]);

}

printf("\n");

}

包含冒泡,选择,插入,shell,快速,合并(归并)排序的原理及其C语言实现,其中归并排序又分为递归和迭代排序算法。代码已通过验证。

#include <stdio.h>

#define N 5

void ShellSort(int a[], int n)

{

int i=0,j=0,temp=0;

int gap = 0;

printf("Start processing function ShellSort()\n"); for (gap=n/2;gap>0;gap/=2)

{

for(i=gap;i<n;i++)

{

temp = a[i];

for (j=i-gap;j>=0;j=j-gap)

{

if (a[j]>temp)

a[j+gap] = a[j];

else

break;

}

a[j+gap] = temp;

}

}

}

void main()

{

int array[N],i;

printf("Please enter %d integers:\n",N);

for (i=0;i<N;i++)

{

scanf("%d",&array[i]);

}

printf("\n");

ShellSort(array,N);

printf("The sorted array is:\n");

for(i=0;i<N;i++)

{

printf("%-5d",array[i]);

}

printf("\n");

}

包含冒泡,选择,插入,shell,快速,合并(归并)排序的原理及其C语言实现,其中归并排序又分为递归和迭代排序算法。代码已通过验证。

// a[]={13,18,17,2,15,4,19}

#include <stdio.h>

#define N 7

int partition(int data[], int low, int high)

{

int temp;

temp = data[low];

while (low<high)

{

while ( (data[high]>temp) && (low<high) ) {

high--;

}

data[low] = data[high];

while ( (data[low]<temp) && (low<high) )

{

low++;

}

data[high] = data[low];

}

data[low] = temp;

return low;

}

void FastSort(int data[], int low, int high)

{

int mid;

if (low<high) // 注意此条件

{

mid = partition(data,low,high);

FastSort(data,low,mid-1);

FastSort(data,mid+1,high);

}

}

void main(void)

{

int a[N];

int i;

printf("Please enter %d integers:\n",N);

for (i=0;i<N;i++)

{

包含冒泡,选择,插入,shell,快速,合并(归并)排序的原理及其C语言实现,其中归并排序又分为递归和迭代排序算法。代码已通过验证。

scanf("%d",&a[i]);

}

FastSort(a,0,N-1);

printf("The sorted array is:\n");

for (i=0;i<N;i++)

{

printf("%-5d",a[i]);

}

printf("\n");

}

6) 合并(归并)排序：递归

// a[]={13,18,17,2,15,4,19}

// a[]={34 23 12 55 66 4 2 99 1 45 77 88 99 5}

#include <stdio.h>

#define N 14

void ArrayMerge(int data[], int low, int mid, int high) {

static int copy_data[N];

int i=low, j=mid+1, k=0;

int ind;

while (i<=mid&&j<=high)

copy_data[k++] = (data[i]<data[j])?data[i++]:data[j++]; if (i>mid)

{

while(j<=high)

copy_data[k++] = data[j++];

}

else

{

while (i<=mid)

copy_data[k++] = data[i++];

}

for (ind=0;ind<k;ind++)

data[ind+low] = copy_data[ind];

}

void MergeSort(int data[], int low, int high)

{

int mid=0;

if (low<high) // 注意此条件

{

mid = (low+high)/2;

包含冒泡,选择,插入,shell,快速,合并(归并)排序的原理及其C语言实现,其中归并排序又分为递归和迭代排序算法。代码已通过验证。

MergeSort(data,low,mid);

MergeSort(data,mid+1,high);

ArrayMerge(data,low,mid,high);

}

}

void main(void)

{

int a[N];

int i;

printf("Please enter %d integers:\n",N);

for (i=0;i<N;i++)

{

scanf("%d",&a[i]);

}

MergeSort(a,0,N-1);

printf("The sorted array is:\n");

for (i=0;i<N;i++)

{

printf("%-5d",a[i]);

}

printf("\n");

}

7) 合并(归并)排序：迭代

// a[]={13,18,17,2,15,4,19}

// a[]={34 23 12 55 66 4 2 99 1 45 77 88 99 5}

#include <stdio.h>

#define N 7

void ArrayMerge(int data[],int low, int mid, int high) {

int copy_data[N];

int i=low, j=mid+1, k=0, ind=0;

while ((i<=mid) && (j<=high))

copy_data[k++] = (data[i]<data[j])?data[i++]:data[j++]; if (i>mid)

{

while (j<=high)

copy_data[k++] = data[j++];

}

else

{

while (i<=mid)

包含冒泡,选择,插入,shell,快速,合并(归并)排序的原理及其C语言实现,其中归并排序又分为递归和迭代排序算法。代码已通过验证。

copy_data[k++] = data[i++]; }

for (ind=0;ind<k;ind++)

data[low+ind] = copy_data[ind]; }

void MergePass(int data[],int s)

{

int i=0;

for (i=0;i<=N-2*s;i=i+2*s)

ArrayMerge(data, i, i+s-1, i+2*s-1); if (N-i>s) // (N-1)-i+1>s

ArrayMerge(data, i, i+s-1, N-1); }

void MergeSort(int data[])

{

int s = 1;

while (s<N)

{

MergePass(data,s);

s=2*s;

}

}

void main(void)

{

int a[N];

int i;

printf("Please enter %d integers:\n",N); for (i=0;i<N;i++)

{

scanf("%d",&a[i]);

}

MergeSort(a);

printf("The sorted array is:\n"); for (i=0;i<N;i++)

{

printf("%-5d",a[i]);

}

printf("\n");

}

本文来源：https://www.bwwdw.com/article/m2bi.html