数组排序（Array Sorting)

大家好，欢迎来到IT知识分享网。

数组排序

对数组排序意味着将数组中的元素按照一定的顺序排列。当前针对数组的排序有许多种排序算法，针对不同的情况，各排序算法之间各有不同。

内部/外部排序

内部排序意味着在排序过程中，参与排序的元素被直接存储在内存中。

外部排序意味着在排序过程中，参与排序的元素被存储在内存之外（诸如本地磁盘），其以小块的形式加载到内存中。外部排序通常适用于当前要排序的数据无法完全加载到内存中，数据量较大的数据。

排序算法稳定性

冒泡排序

冒泡排序是最简单的排序算法：它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。

这种排序方式相对来说效率是比较低下的，因为在排序过程中，它必须多次遍历所有的元素。

冒泡排序算法

int main(){ 
    int arr[100],i,j,temp; printf("输入数组元素数量\n"); scanf("%d",&n); printf ("输入数组元素值\n",n); for(i=0;i<n;i++){ 
    scanf("%d",&arr[i]); } //冒泡排序 for(i=0;i<n-1;i++){ 
    for(j=0;j<n-i-1;j++){ 
    if (arr[j]>arr[j+1]){ 
    temp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp; } } } printf("升序排序"); for (i=0;i<n;i++){ 
    printf("%d\n",att[i]); } return 0; } 

属性

• 平均时间复杂度: O(n^2)
• 稳定性：稳定

使用建议

冒泡排序是一个基本的排序算法，容易理解和使用，且不需要外部存储，所有的操作在内存中进行，但不建议在生产环境中使用该算法。

插入排序

插入排序是一种简单直观且稳定的排序算法。插入排序的基本思想是：每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。假设有一副扑克牌，我们从未排序的卡牌中选择一张，然后将其按照正确的顺序放在手中，依次重复。从未排序的卡牌中抽取一张放在已经排序的手牌中。

排序过程

1. 假设列表中的第一个元素为有序的部分，剩余的为无序部分。
2. 从无序部分列表中去一个元素，按照指定的顺序（升序或者降序列）将该元素插入到已排序的列表中。
   3.重复执行上述过程，直到未排序列表中的所有元素都移动到已排序的列表中为止。

插入排序算法

int main(){ 
    int data[100],n,temp,i,j; printf("输入要排序数组元素的数量"); scanf("%d",&n); printf ("输入数组元素:"); for (i=0;i<n;i++){ 
    scanf("%d",&n); } //插入排序 for (i=1;i<n;i++){ 
    temp=data[i]; j=i-1; while(temp<data[j]&&j>=0){ 
    data[j+1]=data[j]; j=j-1; } data[j+1]=temp; } printf ("排序后的数组"); for (i=0;i<n;i++){ 
    pritf("%d",data[i]); } return 0; } 

属性

• 平均时间复杂度：O(n^2)
• 稳定性：稳定

使用建议

虽然插入排序算法的时间复杂度最坏情况为O(n^2),但是相对于其它排序算法，它在排序过程中要移动的元素较少，因此其性能会好很多。当要排序的数组的元素数量较少时，使用插入排序是比较好的选择，其开销少，消耗内存也少，且简单容易实现。

选择排序

选择排序是一种简单直观的排序算法，它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。

选择排序过程

1. 从列表中选择第一个元素
2. 将所选元素与列表中其它所有元素进行比较
3. 对于每次比较，如果存在任何一个元素小于（或者大于）s所选元素，则交换这两个元素。
4. 对列表的下一个元素重复这个过程，知道整个列表达到有序。

选择排序算法

int main(){ 
    int array[100],n,pos,temp,i,j; printf("输入数组元素数量 \n"); scanf("%d",&n); printf ("输入数组中元素的值\n"); for (i=0;i<n;i++){ 
    scanf("%d",&array[i]); } for (i=0;i<(n-1);i++){ 
    pos=i; for (j=i+1;j<n;j++){ 
    if (array[pos]>array[j]){ 
    pos=j; } } if (pos!=i){ 
    temp=array[i]; array[i]=array[pos]; array[pos]=temp; } } printf("排序后的列表为"); for (i=0;i<n;i++){ 
    printf("%d \n",array[i]); } return 0; } 

属性

• 平混时间复杂度:O(n^1)
• 稳定性：不稳定

使用建议

选择排序不受数组中元素的初始顺序影响，可以用来对小列表数组进行排序。在所有排序算法中，它执行的数据移动量是最小的，因此可以在处理数据成本很高的情况下使用这种排序算法。

快速排序

快速排序是对冒泡排序的一种改进，它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

排序过程

1. 选定一个元素，作为分界值，通过该分界值将数组分为两个部分。
2. 对数组重新排序，使所有小于分界值的元素在分界之前，而所有大于分界值的元素在分界值之后。此时，左边界中各部分元素值均小于右边界各部分元素值。
3. 然后，左边和右边的数据再进行独立排序。对于左侧的数组数据，再取一个分界值，将小于该分界值的值至于该分界左边，大于该分界值的值置于该分界值右边。右边的值也做类似处理。
4. 重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序之后，再递归排好右边界各个部分数据。自此，整个数组的排序就完成了。

快速排序算法

void swap(int a,int b){ 
    int t=a; a=b; b=t; } //划分界限 int partition(int arr[],int low,int high){ 
    int pivot=arr[hight];//pivot int i=(low-1);//数组的最小索引 for (int j=low;j<=high-1;j++){ 
    if (arr[j]<pivot){ 
    i++; swap(&arr[i],&arr[j]); } } swap(&arr[i+1],&arr[higt]); return (i+1); } //快速排序 void quick_sort(int arr[],int low,int high){ 
    if (low<high){ 
    int pi=partition(atr,low,high); quick_sort(arr,low,pi-1); quick_sort(arr,pi+1,high); } } int main(){ 
    int a[100],n,i; printf("要排序数组元素的数量"); scanf("%d",&n); printf ("输入数组元素:\n"); for (i=0;i<n;i++){ 
    scanf("%d",&a[i]); } quick_sort("排序后的数组"); for (i=0;i<n;i++){ 
    printf("%d",a[i]); } return 0; } 

属性

• 平均时间复杂度:O(n log n)
• 稳定性：不稳定

使用建议

快速排序是性能最好的排序算法，它可以有效的对任何数据进行排序。快速排序被认为是目前最好的内部排序算法，其不需要使用任何额外的内存来执行排序。如果选择的分界算法有效，那么快速排序是最通用的排序算法之一。

归并排序

归并排序是建立在归并操作上的一种有效的排序算法，该算法采用分治法的一种典型应用，通过重复的将数组分成若干小部分，然后按照排序的顺序将其再次合并。

排序过程

1. 将未排序的列表分为n个子列表，每个子列表包含一个元素
2. 重复合并子列表以产生新的排序子列表，直到仅剩下一个子列表，即为最终的排序列表，合并排序列表即可。

归并排序算法

void merger(int a[],int i1,int j1,int i2,int j2){ 
    int temp[50]; int i,j,k; i=i1; j=12; k=0; while(i<=j1&&j<=j2>){ 
    if (a[i]<a[j]>){ 
    temp[k++]=a[i++]; }else{ 
    temp[k++]=a[j++]; } while(i<=j1){ 
    temp[k++]=a[i++]; } while(j<=j2){ 
    temp[k++]=a[j++]; } for(i=i1,j=0;i<j2;i++,j++){ 
    a[i]=temp[j]; } } } void mergesort(int a[],int i,int j){ 
    int mid; if (i<j){ 
    mid=(i+j)/2; mergesort(a,i,mid); mergesort(a,mid+1,j); merge(a,i,mid,mid+1,j); } } int main(){ 
    int a[30],n,i; printf("输入要排序数组元素数量:"); scanf("%d",&n); printf("输入数组元素"); for(i=0;i<n;i++){ 
    scanf("%d",&a[i]); } mergesort(a,0,n-1); printf("排序后的数组是:"); for(i=0i<n;i++){ 
    printf("%d",a[i]); } return 0; } 

属性

• 平均时间复杂度:O(n log n)
• 稳定性：稳定

使用建议

这种排序可以用在任意大小的数组上，不像其它排序算法一样，只在较小的集合上有较好的性能。

更多内容，欢迎关注：