数组排序方法及C实现的总结（转载）
数组排序方法及C实现的总结cintegernumbersinput算法n2
目录(?)[+]
1、问题描述
数组排序（即按某种特定的顺序排列数据，如升序或降序）是最重要的计算应用之一，银行用帐号对所有的支票进行能够排序，并根据排序结果准备月底的财务报告，学校学生成绩管理系统用数组排序的方法将考试成绩从高到低进行排名，数组排序方法很多，有直接插入排序、冒泡排序、快速排序、直接选择排序，下面来详细介绍这四种基本的排序方法及其实现。
2、方法总结
1）直接插入排序：数据表A中每个元素距其最终位置不远，数据表A按关键字值基本有序，可用此方法排序较快。
2）冒泡排序法：将较小的值“上浮”到数组顶部，而较大值“下沉”到数组底部，这种排序技术要比较好几趟，每一趟要比较连续的数组元素对，如果某对数值是按升序排序的（或者这两个值相等），那就保持原样，如果某对数组是按降序排列的，就要交换它们的值。
3）快速排序法：快速排序是对冒泡排序的一种改进。它的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
4）直接选择排序法：直接选择排序的作法是：第一趟扫描所有数据，选择其中最小的一个与第一个数据互换；第二趟从第二个数据开始向后扫描，选择最小的与第二个数据互换；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。它比起冒泡排序有一个优点就是不用不断的交换。
3、算法实现
1）直接插入法实现
#include<stdio.h>
#include<conio.h>
int main()
{
void InsertSort(int [],int);
int a={8,10,2,3,1,7,13};
int i;
InsertSort(a,7);
for(i=0;i<7;i++)
printf("%4d",a);
getch();
}
void InsertSort(int a[],int count)
{
int i,j,temp;
for(i=1;i<count;i++)
{
temp=a;
j=i-1;
while(a>temp && j>=0)
{
a=a;
j--;
}
if(j!=(i-1))
a=temp;
}
}
2）冒泡法实现
#include<stdio.h>
#include<conio.h>
int main()
{
void BubbleSort(int []);
int a;
int i,j,temp;
printf("Input tem integer numbers for a:");
for(i=0;i<10;i++)
scanf("%d,",&a);
printf("\n");
BubbleSort(a);
printf("The sorted array is:\n");
for(j=0;j<10;j++)
printf("%d,",a);
printf("\n\n");
getch();
}
void BubbleSort(int array[])
{
int i,j,temp;
for(j=0;j<9;j++)
for(i=0;i<9-j;i++)
if(array>array)
{
temp=array;
array=array;
array=temp;
}
}
3）快速排序法实现
#include<stdio.h>
#include<conio.h>
#define Max 8
int main()
{
void QuickSort(int a[],int p,int r);
int a[]={2,8,7,1,3,5,6,4};
QuickSort(a,1,Max);
printf(" The sorted array is :");
for(int i=0;i<Max;i++)
printf("%d,",a);
printf("\n");
getch();
}
void QuickSort(int a[],int p,int r)
{
int Partition(int a[],int p,int r);
if(p<r)
{
int q=Partition(a,p,r);
QuickSort(a,p,q-1);
QuickSort(a,q+1,r);
}
}
int Partition(int a[],int p,int r)
{
int i=p-1;
int x=a;
for(int j=p;j<r;j++)
{
if(a<=x)
{
i=i+1;
int temp;
temp=a;
a=a;
a=temp;
}
}
int temp;
temp=a;
a=a;
a=temp;
return i+1;
}
4）直接选择法实现
#include<stdio.h>
#include<conio.h>
int main()
{
void ChooseSort(int []);
int i,j,a;
printf("Input ten integer numbers for a: ");
for(i=0;i<10;i++)
scanf("%d,",&a);
printf("\n");
ChooseSort(a);
printf("The sorted array is:\n");
for(j=0;j<10;j++)
printf("%d,",a);
printf("\n\n");
getch();
}
void ChooseSort(int array[])
{
int j,temp,*p1,*p2;
for(p1=array;p1<array+9;p1++)
{
j++;
for(p2=array+j;p2<=array+9;p2++)
if(*p2<*p1)
{
temp=*p2;
*p2=*p1;
*p1=temp;
}
}
}
4、各种方法比较
1）时间性能比较
按平均的时间性能来分，四种类排序方法时间复杂度分别为：
直接插入排序法：O(n^2)
冒泡排序法：O(n^2)
快速排序法：O(nlogn)
直接选择排序法：O(n^2)
时间复杂度为O(n^2)的有：直接插入排序、起泡排序和简单选择排序，其中以直接插入为最好，特别是对那些对关键字近似有序的记录序列尤为如此；当待排记录序列按关键字顺序有序时，直接插入排序和起泡排序能达到O(n)的时间复杂度;而对于快速排序而言，这是最不好的情况，此时的时间性能蜕化为O(n2)，因此是应该尽量避免的情况。
2）排序方法的稳定性能比较
1.稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。
2.当对多关键字的记录序列进行LSD方法排序时，必须采用稳定的排序方法。
3.对于不稳定的排序方法，只要能举出一个实例说明即可。
4.快速排序是不稳定的排序方法。 以前考数据库的时候搞过，现在都忘记了！ LZ少了一个最快的方法。归并排序是所有方法中最快的，它只需要扫描log2(n)次数组就够了。在我的试验中，归并排序在排列随机数时效率最高，其它任何方法都比不上归并排序。 wye11083 发表于 2013-6-29 11:43 static/image/common/back.gif
LZ少了一个最快的方法。归并排序是所有方法中最快的，它只需要扫描log2(n)次数组就够了。在我的试验中，归 ...
感谢提醒，加入归并排序：（同样是转载）
归并排序
归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
假设我们有一个没有排好序的序列，那么首先我们使用分割的办法将这个序列分割成一个一个已经排好序的子序列，然后再利用归并的方法将一个个的子序列合并成排序好的序列。分割和归并的过程可以看下面的图例。
从上图可以看出，我们首先把一个未排序的序列从中间分割成2部分，再把2部分分成4部分，依次分割下去，直到分割成一个一个的数据，再把这些数据两两归并到一起，使之有序，不停的归并，最后成为一个排好序的序列。
如何把两个已经排序好的子序列归并成一个排好序的序列呢？可以参看下面的方法。
假设我们有两个已经排序好的子序列。
序列A：1 23 34 65
序列B：2 13 14 87
那么可以按照下面的步骤将它们归并到一个序列中。
（1）首先设定一个新的数列C。
（2）A和B比较，A = 1，B = 2，A < B，那么C = 1
（3）A和B比较，A = 23，B = 2，A > B，那么C = 2
（4）A和B比较，A = 23，B = 13，A > B，那么C = 13
（5）A和B比较，A = 23，B = 14，A > B，那么C = 14
（6）A和B比较，A = 23，B = 87，A < B，那么C = 23
（7）A和B比较，A = 34，B = 87，A < B，那么C = 34
（8）A和B比较，A = 65，B = 87，A < B，那么C = 65
（9）最后将B复制到C中，那么C = 87。归并完成。
C代码：
//归并排序中的合并算法
void Merge(int array[], int start, int mid, int end)
{
int temp1, temp2;
int n1, n2;
n1 = mid - start + 1;
n2 = end - mid;
//拷贝前半部分数组
for (int i = 0; i < n1; i++)
temp1 = array;
//拷贝后半部分数组
for (int i = 0; i < n2; i++)
temp2 = array;
//把后面的元素设置的很大
temp1 = temp2 = 1000;
//逐个扫描两部分数组然后放到相应的位置去
for (int k = start, i = 0, j = 0; k <= end; k++)
{
if (temp1 <= temp2)
{
array = temp1;
i++;
}
else
{
array = temp2;
j++;
}
}
}
//归并排序
void MergeSort(int array[], int start, int end)
{
if (start < end)
{
int i;
i = (end + start) / 2;
//对前半部分进行排序
MergeSort(array, start, i);
//对后半部分进行排序
MergeSort(array, i + 1, end);
//合并前后两部分
Merge(array, start, i, end);
}
}
归并排序是稳定的，它的最差，平均，最好时间都是O(nlogn)。但是它需要额外的存储空间，这在某些内存紧张的机器上会受到限制。
归并算法是又分割和归并两部分组成的。对于分割部分，如果我们使用二分查找的话，时间是O(logn)，在最后归并的时候，时间是O(n)，所以总的时间是O(nlogn)。
嗯嗯，很精彩的帖子 顶，不错，谢。
mark……
顶一个…
页:
[1]