数组排序(C 语言实现)

本文主要包含常见的数组排序方法。

选择排序

原理

1. 在原始数组中取未排序的首元素，与其后方所有元素比较，不满足顺序，则交换
2. 首元素此时满足条件，未排序部分后移
3. 重复上述操作

代码实现

#include <stdio.h>
#include <stdlib.h>

void SelectSort(int *p,int n)
{
    for(int i=0;i<n-1;i++)
        for(int j=i+1;j<n;j++)
            if(p[i]<p[j])
            {
                p[i] = p[i]^p[j];
                p[j] = p[i]^p[j];
                p[i] = p[i]^p[j];
            }
}

int main(void)
{
    int arr[10] = {1,5,9,6,4,3,2,7,8,0};

    SelectSort(arr,10);

    for(int i=0;i<10;i++)
        printf("%d\n",arr[i]);

    return 0;
}

结果为：

9
8
7
6
5
4
3
2
1
0

改进

如果觉得每次交换很麻烦，可以先找出每次迭代的最大值，然后再交换位置，这样交换次数少，在数据量比较大时效率比较高。

#include <stdio.h>
#include <stdlib.h>

void SelectSort(int *p,int n)
{
    int max;
    for(int i=0;i<n-1;i++)
    {
        max = i;
        for(int j=i+1;j<n;j++)
            if(p[max]<p[j])
                max = j;
        if(max!=i)
        {
            p[i] = p[i]^p[max];
            p[max] = p[i]^p[max];
            p[i] = p[i]^p[max];
        }
    }
}

int main(void)
{
    int arr[10] = {1,5,9,6,4,3,2,7,8,0};

    SelectSort(arr,10);

    for(int i=0;i<10;i++)
        printf("%d\n",arr[i]);

    return 0;
}

结果为：

9
8
7
6
5
4
3
2
1
0

冒泡排序

原理

1. 从头开始，比较相邻的两个元素，如果不满足顺序，则交换
2. 此时有一个元素的位置确定，不再参加下轮比较
3. 重复上述操作

代码实现

#include <stdio.h>
#include <stdlib.h>

void PopSort(int *p,int n)
{
    for(int i=0;i<n-1;i++)
        for(int j=0;j<n-i-1;j++)
            if(p[j]<p[j+1])
            {
                p[j] = p[j]^p[j+1];
                p[j+1] = p[j]^p[j+1];
                p[j] = p[j]^p[j+1];
            }
}

int main(void)
{
    int arr[10] = {1,5,9,6,4,3,2,7,8,0};

    PopSort(arr,10);

    for(int i=0;i<10;i++)
        printf("%d\n",arr[i]);

    return 0;
}

结果为：

9
8
7
6
5
4
3
2
1
0

改进

如果当前迭代的元素已经有序，就说明整体已经有序，无须进行下次迭代。

#include <stdio.h>
#include <stdlib.h>

void PopSort(int *p,int n)
{
    int flag;
    for(int i=0;i<n-1;i++)
    {
        flag = 0;
        for(int j=0;j<n-i-1;j++)
            if(p[j]<p[j+1])
            {
                p[j] = p[j]^p[j+1];
                p[j+1] = p[j]^p[j+1];
                p[j] = p[j]^p[j+1];
                flag = 1;
            }
        if(!flag)
            break;
    }
}

int main(void)
{
    int arr[10] = {1,5,9,6,4,3,2,7,8,0};

    PopSort(arr,10);

    for(int i=0;i<10;i++)
        printf("%d\n",arr[i]);

    return 0;
}

结果为：

9
8
7
6
5
4
3
2
1
0

快速排序

原理

1. 从数组中挑选一个元素作为基准
2. 分组。所有比基准小的位于基准的左侧，比基准大的位于基准的右侧
3. 以递归方式分别对基准两侧的序列进行排序

代码实现

#include <stdio.h>
#include <stdlib.h>

void QuickSort(int *p,int low,int high)
{
    int l = low,h = high;
    int std = p[low];
    if(low<high)
    {
        while(l<h)
        {
            if(p[h]>=std && l<h)
                h--;
            p[l] = p[h];
            if(p[l]<std && l<h)
                l++;
            p[h] = p[l];
        }

        p[l] = std;
        QuickSort(p,low,l-1);
        QuickSort(p,l+1,high);
    }
}

int main(void)
{
    int arr[10] = {1,5,9,6,4,3,2,7,8,0};

    QuickSort(arr,0,9);

    for(int i=0;i<10;i++)
        printf("%d\n",arr[i]);

    return 0;
}

结果为：

0
1
2
3
4
5
6
7
8
9