首頁 > 軟體

C語言中陣列排序淺析

2022-12-15 14:01:05

前言

本文介紹了幾種c語言中對亂序陣列的排序方式。

具體的內容有:

  • 插入排序;
  • 氣泡排序;
  • 選擇排序;
  • 希爾排序;

具體內容詳見下文。

一、插入排序

1、思路

首先假設陣列的的前n位元素是有序的,然後從第n+1位開始,將此元素插入到前面,使得前n+1位元素有序,以此類推,直至整個陣列有序。

在對第n+1位元素操作時,使用臨時變數存放該元素的值,從第n位元素開始向前比較,同時將與其比較的元素向後移動,直到與其比較的元素比其小時,將臨時變數中的值放入該元素後的一個陣列元素中。

2、具體步驟

1.從第一個元素開始,該元素可以認為已經被排序。

2.取下一個元素存入臨時變數temp,對前方有序序列從後往前掃描。

3.如果該元素大於temp,則將該元素移到下一位。

4.重複步驟3,直到找到已於等於temp的元素。

5.temp插入到該元素的後面一位,如果所有有序元素都大於temp,則將temp插入到下標為0的位置(既陣列的首位,說明該元素是目前最小的元素)。

6.重複以上的2~5步驟,直至操作完整個陣列中的所有元素。

3、程式碼實現

void insertsort(int arr[], int len)
{
	int j;
	for(j=0; j<len-1; j++)
	{
		int end=j;    //前end位為有序部分
		int temp=arr[j+1];    //臨時變數存放
		while(end>=0)
		{
			if(arr[end]>temp)    //將temp變數與前面一位元素比較
			{
				arr[end+1]=arr[end];    //將比temp變數大的元素向後移動一位
				end--;    //繼續向前比較
			}
			else    //找到比temp變數小的元素
			{
				break;
			}
		}
		arr[end+1]=temp;    //將temp變數插入有序部分
	}
}

4、複雜度

時間複雜度: O(N)~O(N^2)

空間複雜度:O(1)

二、氣泡排序

1、思路

通過對陣列內相鄰元素的比較,使較大的元素向後移動,較小的元素向前移動,不斷迴圈此過程,直至整個陣列有序。

當第n次迴圈結束後,陣列的最後n位為有序,所以每回圈一次,就可以將回圈的範圍(後界)向前減少一位元素。

2、具體步驟

1.將陣列中的第一個元素與下一個元素進行比較,若第一個元素較大,則交換位置。

2.繼續比較下兩個元素的大小,將較大的元素放在靠後的位置。

3.重複步驟2,直至完成第n-1個元素與第n個元素的比較。

4.將回圈的後界減一,重複1~5步驟。

5.當迴圈的範圍減為1時,此時的為有序陣列。

3、程式碼實現

void bubblesort(int arr[], int len)
{
	int j,k;    //定義迴圈因子,巢狀雙層迴圈
	for(j=0; j<len-1; j++)    //設定迴圈後界
	{
		for(k=0; k<len-j-1; k++)    //不斷向後進行比較
		{
			if(arr[k]>arr[k+1])    //比較相鄰的元素
			{
				int temp=arr[k];    //三杯水交換法
				arr[k]=arr[k+1];
				arr[k+1]=temp;
			}
		}
	}
}

4、複雜度

時間複雜度: O(N)~O(N^2)

空間複雜度: O(1)

三、選擇排序

1、思路

不斷掃描陣列,每次選出一個最小值和一個最大值,分別放在序列的首位置和末位置,然後將序列的首位置與末位置分別向後與前移動一位。直至排完整個陣列。

2、具體步驟

1.定義序列的首末位置。

2.掃描首末位置之間的序列,選出一個最小值min和一個最大值max,記錄下標值。

3.將最小值放入首位置start,最大值放入末位置end。

4.將首位置向後移動一位,末位置向前移動一位。

5.重複2~4步驟,直至首末位置重合(start>=end),此時的陣列為有序陣列。

3、程式碼實現

void selectsort(int arr[], int len)
{
	int start=0, end=len-1;    //定義首末位置
	while(start<end)
	{
		int max=start;    
		int min=start;
		int j;
		for(j=start; j<=end; j++)    //掃描首末位置之間的序列
		{
			if (arr[j] < arr[min])    //選取最小值
			{
				min = j;    //記錄最小值的下標
			}
			if (arr[j] > arr[max])    //選取最大值
			{
				max = j;    //記錄最大值的下標
			}
		}
		int temp=arr[min];    //三杯水交換,將最小值放入首位置
		arr[min]=arr[start];
		arr[start]=temp;
		if (start == max)    //防止最大值在首位置被換走
		{
			max = min;
		}
		temp=arr[max];    //三杯水交換,將最大值放入末位置
		arr[max]=arr[end];
		arr[end]=temp;
		start++;    //首位置後移一位
		end--;    //末位置前移一位
	}
}

4、複雜度

時間複雜度: O(N^2)

空間複雜度: O(1)

四、希爾排序

1、思路

定義一個小於陣列長度增量,將整個陣列中每隔一個增量的元素分為一組,對每組中的元素進行插入排序,再將增量減小,之後重複以上過程,直至增量減小為1時,對已經進行過預處理的陣列進行插入排序,達到減小複雜度的目的。

2、具體步驟

1.定義一個小於陣列長度的增量gap(通常為陣列長度的一半),將陣列進行分組。

2.對每組中的元素進行插入排序的操作,使之有序。

3.減小增量gap(通常為減為一半),將陣列再度細分。

4.重複2~3步驟,直至增量gap減小為1。

5.此時對整個陣列再做插入排序操作,使整個陣列有序。

3、程式碼實現

void shellsort(int arr[], int len)
{
	int gap=len;    //定義增量
	while(gap>1)
	{
		gap=gap/2;    //將增量減小
		int j;
		for(j=0; j<len-gap; j++)    //將陣列分組
		{
			int end=j;
			int temp=arr[end+gap];    //對每組元素進行插入排序
			while(end>=0)
			{
				if(arr[end]>temp)
				{
					arr[gap+end]=arr[end];
					end-=gap;
				}
				else
				{
					break;
				}
			}
			arr[end+gap]=temp;
		}
	}
}

4、複雜度

時間複雜度: 平均 O(N^1.3)

空間複雜度: O(1)

具體使用

#include<stdio.h>
void insertsort(int arr[], int len)    //選擇排序
{
	int j;
	for(j=0; j<len-1; j++)
	{
		int end=j;
		int temp=arr[j+1];
		while(end>=0)
		{
			if(arr[end]>temp)
			{
				arr[end+1]=arr[end];
				end--;
			}
			else
			{
				break;
			}
		}
		arr[end+1]=temp;
	}
}
void bubblesort(int arr[], int len)    //氣泡排序
{
	int j,k;
	for(j=0; j<len-1; j++)
	{
		for(k=0; k<len-j-1; k++)
		{
			if(arr[k]>arr[k+1])
			{
				int temp=arr[k];
				arr[k]=arr[k+1];
				arr[k+1]=temp;
			}
		}
	}
}
void shellsort(int arr[], int len)    //希爾排序
{
	int gap=len;
	while(gap>1)
	{
		gap=gap/2;
		int j;
		for(j=0; j<len-gap; j++)
		{
			int end=j;
			int temp=arr[end+gap];
			while(end>=0)
			{
				if(arr[end]>temp)
				{
					arr[gap+end]=arr[end];
					end-=gap;
				}
				else
				{
					break;
				}
			}
			arr[end+gap]=temp;
		}
	}
}
void selectsort(int arr[], int len)    //選擇排序
{
	int start=0, end=len-1;
	while(start<end)
	{
		int max=start;
		int min=start;
		int j;
		for(j=start; j<=end; j++)
		{
			if (arr[j] < arr[min])
			{
				min = j;
			}
			if (arr[j] > arr[max])
			{
				max = j;
			}
		}
		int temp=arr[min];
		arr[min]=arr[start];
		arr[start]=temp;
		if (start == max)
		{
			max = min;
		}
		temp=arr[max];
		arr[max]=arr[end];
		arr[end]=temp;
		start++;
		end--;
	}
}
int main()
{
	int arr[10]={9,8,7,6,5,4,3,2,1,0};    //亂序陣列
	int len=sizeof(arr)/4;
	int i;
	for(i=0; i<len; i++)
	{
		printf("%dt", arr[i]);    //輸出初始陣列,用於比較
	}
	putchar('n');
	selectsort(arr, len);    //呼叫函數對陣列進行排序,這裡選用的是選擇排序的方式
	for(i=0; i<len; i++)
	{
		printf("%dt", arr[i]);    //輸出排完序後的陣列
	}
	putchar('n');
	return 0;
 } 

例題及其解答

題目描述

來源:牛客網

小明平時學習太用功了,閒暇時間就喜歡玩一種數位遊戲,在這個遊戲中,他每次會使用n個正整數先構造一個數列(x1,……,xn),並可以根據需要無限次執行以下操作:

選擇兩個不同的i,j,其中xi>xj,然後將xi改為xi-xj。

請你幫小明算一下,通過這樣的一系列操作,求出最終處理過數列的總和最小值是多少?

輸入描述

第一行一個整數n代表數列的長度,2<=n<=100,

第二行包含n個正整數x1 x2 x3 ... xi, 1<=xi<=100.

輸出描述

經過多次操作後,數列總和的最小值(整數)。

範例1

輸入

5
45 12 27 30 18

輸出

15

範例2

輸入

3 2 4 6

3
2 4 6

輸出

6

說明

在輸出樣例2中進行了以下操作:x3 = x3 - x2, x2 = x2 - x1,經過這兩步操作後,所有的數位都相等,因此操作不能再進行下去了,每個數都是2,因此6就是總和的最小值。

解答

#include<stdio.h>
void sort(int arr[], int n)    //本題我使用的是氣泡排序,也可使用其他排序方式
{
    int i,j;
    for(i=0; i<n-1; i++)
    {
        for(j=0; j<n-1-i; j++)
        {
            if(arr[j]<arr[j+1])
            {
                int temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
            }
        }
    }
}
int main()
{
    int n;
    scanf("%d",&n);    //輸入數列長度
    int arr[n];    //定義相應長度的陣列
    int i;
    for(i=0; i<n; i++)
    {
        scanf("%d", &arr[i]);    //將輸入的資料存入陣列
    }
    while(1)
    {
        sort(arr,n);    //對陣列進行排序
        if(arr[0]==arr[n-1])    //判斷陣列的首末元素是否相等
        {
            break;    //若相等,則無法再進行作差操作
        }
        for(i=0;i<n-1; i++)    //對陣列中的相鄰且不相等的元素作差
        {
            if(arr[i]>arr[i+1])
            {
                arr[i]=arr[i]-arr[i+1];
            }
        }
    }
    int sum=0;
    for(i=0; i<n; i++)    //對最終的陣列進行求和
    {
        sum=sum+arr[i];
    }
    printf("%dn", sum);    //輸出答案
    return 0;
}

結語

以上就是四種陣列排序方式的全部內容,以及在例題中的應用。

到此這篇關於C語言中陣列排序淺析的文章就介紹到這了,更多相關C語言陣列排序內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com!


IT145.com E-mail:sddin#qq.com