C語言中數(shù)組常用的一些排序算法小結

更新時間：2024年01月11日 10:28:50 作者：豬兒蟲21

數(shù)組的排序方法有很多,效率也各不相同,下面這篇文章主要給大家介紹了關于C語言中數(shù)組常用的一些排序算法的相關資料,文中通過代碼介紹的非常詳細,需要的朋友可以參考下

一.C語言中數(shù)組的一些算法

把數(shù)據(jù)按照從小到大或從大到小的順序進行排列

有很多算法：冒泡排序、選擇排序、插入排序、快速排序、計數(shù)排序、堆排序 .......

常用的有四種：

1.1冒泡排序

主要思想：

總共需要比較n-1輪

每一輪依次比較當前元素和后面的元素，如果當前元素比后面元素大，則交換他們的位置

一輪下來，最大的元素放在了數(shù)組最后面

int a[10] = {50,23,80,18,100,5,10,58,30,2};
第一輪:
23,50,18,80,5,10,58,30,2,100
第二輪:
23,18,50,5,10,58,30,2,80,100
......
for(i=0;i<10-1;i++)//比較10-1輪
{
for(j=0;j<10-1-i;j++)
{
if(a[j] > a[j+1])
{
//交換
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}

1.2選擇排序

總共需要比較n-1輪

每一輪比較最多只交換一次數(shù)據(jù)（把最大數(shù)字放在最后面位置或把最小的數(shù)字放在最前面位置）

#include<stdio.h>
int main()
{
    int a[10] = {50,23,80,18,100,5,10,58,30,2};
    int i,j;
    int temp;
    for(i=0;i<10-1;i++)//進行n-1輪比較
    {
        int max = a[0];//假設最大的數(shù)字是a[0]
        int index = 0;//用來保存最大值的下標
        for(j=0;j<10-i;j++)//每一輪比較把最大的數(shù)字放在最后面
        {
            if(a[j] > max)
            {
                max = a[j];
                index = j;
            }
        }
        //至此我們已經(jīng)最大值為 max, 他的下標為index ，交換 a[index] 所在元素和 a[9-i]
        if(index != 9-i)
        {
            temp = a[index];
            a[index] = a[9-i];
            a[9-i] = temp;
        }
    }
    for(i=0;i<10;i++)
    {
        printf("%d ",a[i]);
    }
    printf("\n");
    return 0;
 }

類似的，把最小的放后面：

#include<stdio.h>
int main()
{
    int a[10] = {50,23,80,18,100,5,10,58,30,2};
    int i,j;
    int temp;
    for(i=0;i<10-1;i++)
    {
        //每一輪比較把最小的數(shù)字放在最前面
        int min = a[9];
        int index = 9;
        for(j=0+i;j<10;j++)
        {
            if(a[j]<min)
            {
                min = a[j];
                index = j;
            }
        }
        //至此我們已知最小值為 min ，他的下標為index ，交換 a[index] 所在元素和 a[i]
        if(index != i)
        {
            temp = a[index];
            a[index] = a[i];
            a[i] = temp;
        }
    }
    for(i=0;i<10;i++)
    {
        printf("%d ",a[i]);
    }
    printf("\n");
    return 0;
}

1.3插入排序

算法思想：直接插入排序是無序序列插入到有序序列中，通常假定a[0]為已經(jīng)排好序的子序列，然后將剩下無序序列一個一個插入到有序的子序列中。適用于基本有序和數(shù)據(jù)量不大的情況。

#include<stdio.h>
#include<math.h>
int main()
{
    int a[10] = {999,10,15,18,5,30,80,26,345,-10};
    int i,j;
    for(i=1;i<10;i++)//總共需要插入9輪
    {
        //把 a[i] 插入到前面的有序集合中，使之仍然有序
        int data = a[i];
        for(j=i-1;j>=0;j--)
        {
            if(a[j]>data)
            {
                a[j+1] = a[j];
            }
            else
            {
                a[j+1] = data;
                break;
            }
        }
        if(j==-1)
        {
            a[0] = data;
        }
    }
    for(i=0;i<10;i++)
    {
        printf("%d ",a[i]);
    }
    printf("\n");
}

1.4快速排序

1先從數(shù)組中選取一個數(shù)作為基準點，可隨機選擇；

2 將數(shù)組中大于該基準點的放在該基準點右邊，小于該基準點的放在該基準點左邊；

3 對左右兩個數(shù)組進行快速排序。

代碼示例：

#include <stdio.h>
//快速排序 有左右兩邊 因此我需要傳進來左右的下標
void FastSort(int a[],int left,int right)
{
    //當左邊比右邊不得小 我們就沒有必要排序了
    if(left >= right)
        return;
    int l = left;
    int r = right;
    //設置基準點 我這里設置的是第一個
    int temp = a[left];
    //將我們的數(shù)組進行一次快排
    //將temp的左邊變得都比temp小，右邊都比temp大
    while(l < r)
    {
        //由于你的基準點是在左邊第一個  因此首先就要從右邊找到左邊
        //將右邊小于基準點的元素弄到左邊去
        for(;r > l;r--)
        {
            if(temp > a[r])
            {
                //將這個小一點的數(shù)弄到左邊去
                a[l] = a[r];
                break;
            }
        }
        //然后從左邊找到右邊去 找到比基準點大的 放在右邊去
        for(;r > l;l++)
        {
            if(temp < a[l])
            {
                //將大的數(shù)弄到右邊去
                a[r] = a[l];
                break;
            }
        }        
    }
    a[l] = temp;//恢復基準點
    //以相同的規(guī)則將左邊的排序
    FastSort(a,left,l - 1);
    //以相同的規(guī)則將右邊排序
    FastSort(a,r + 1,right);
}
//打印數(shù)組
void PrintArr(int arr[],int n)
{
    for(int i = 0;i < n;i++)
        printf("%d ",arr[i]);
    printf("\n");
}
int main()
{
    int a[] = {12378,34,412,453,34,25,4,432,5,43};
    FastSort(a,0,sizeof(a) / sizeof(a[0]) - 1);
    PrintArr(a,sizeof(a) / sizeof(a[0]));
    return 0;
}

附：C 語言利用數(shù)組，按從小到大的順序排列好n個數(shù)，并輸出新序列

利用數(shù)組排序，可以考慮冒泡排序

冒泡排序是最簡單的交換排序方法，通過兩兩比較關鍵字，如果發(fā)生逆序，就進行交換，從而使關鍵字小的記錄像氣泡一樣往上“漂浮”，或者使關鍵字打的記錄往下“墜落”

#include<stdio.h>
int main()
{
	int i, j, n, temp;
	int arr[10];
	for (i = 0; i < 10; i++)
		scanf_s("%d", &arr[i]);
	for (i = 0; i < 10; i++)
	{
		for (j = 0; j < 10 - i-1; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
	printf("\n");
	for (i = 0; i < 10; i++)
		printf("%d ", arr[i]);
	return 0;

}

運行結果：隨意輸入10個數(shù)字

5 45 56 123 456 789 58 989 785 653

5 22 45 56 58 123 456 653 785 789
--------------------------------
Process exited after 20.02 seconds with return value 0
請按任意鍵繼續(xù). . .