C語言中數(shù)組排序淺析
前言
本文介紹了幾種c語言中對亂序數(shù)組的排序方式。
具體的內(nèi)容有：
- 插入排序；
- 冒泡排序；
- 選擇排序；
- 希爾排序；
具體內(nèi)容詳見下文。
一、插入排序
1、思路
首先假設(shè)數(shù)組的的前n位元素是有序的，然后從第n+1位開始，將此元素插入到前面，使得前n+1位元素有序，以此類推，直至整個數(shù)組有序。
在對第n+1位元素操作時，使用臨時變量存放該元素的值，從第n位元素開始向前比較，同時將與其比較的元素向后移動，直到與其比較的元素比其小時，將臨時變量中的值放入該元素后的一個數(shù)組元素中。
2、具體步驟
1.從第一個元素開始，該元素可以認為已經(jīng)被排序。
2.取下一個元素存入臨時變量temp，對前方有序序列從后往前掃描。
3.如果該元素大于temp，則將該元素移到下一位。
4.重復步驟3，直到找到已于等于temp的元素。
5.temp插入到該元素的后面一位，如果所有有序元素都大于temp，則將temp插入到下標為0的位置（既數(shù)組的首位，說明該元素是目前最小的元素）。
6.重復以上的2~5步驟，直至操作完整個數(shù)組中的所有元素。
3、代碼實現(xiàn)
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--; //繼續(xù)向前比較
}
else //找到比temp變量小的元素
{
break;
}
}
arr[end+1]=temp; //將temp變量插入有序部分
}
}4、復雜度
時間復雜度： O（N）~O（N^2）
空間復雜度：O（1）
二、冒泡排序
1、思路
通過對數(shù)組內(nèi)相鄰元素的比較，使較大的元素向后移動，較小的元素向前移動，不斷循環(huán)此過程，直至整個數(shù)組有序。
當?shù)趎次循環(huán)結(jié)束后，數(shù)組的最后n位為有序，所以每循環(huán)一次，就可以將循環(huán)的范圍（后界）向前減少一位元素。
2、具體步驟
1.將數(shù)組中的第一個元素與下一個元素進行比較，若第一個元素較大，則交換位置。
2.繼續(xù)比較下兩個元素的大小，將較大的元素放在靠后的位置。
3.重復步驟2，直至完成第n-1個元素與第n個元素的比較。
4.將循環(huán)的后界減一，重復1~5步驟。
5.當循環(huán)的范圍減為1時，此時的為有序數(shù)組。
3、代碼實現(xiàn)
void bubblesort(int arr[], int len)
{
int j,k; //定義循環(huán)因子，嵌套雙層循環(huán)
for(j=0; j<len-1; j++) //設(shè)置循環(huán)后界
{
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、思路
不斷掃描數(shù)組，每次選出一個最小值和一個最大值，分別放在序列的首位置和末位置，然后將序列的首位置與末位置分別向后與前移動一位。直至排完整個數(shù)組。
2、具體步驟
1.定義序列的首末位置。
2.掃描首末位置之間的序列，選出一個最小值min和一個最大值max，記錄下標值。
3.將最小值放入首位置start，最大值放入末位置end。
4.將首位置向后移動一位，末位置向前移動一位。
5.重復2~4步驟，直至首末位置重合（start>=end），此時的數(shù)組為有序數(shù)組。
3、代碼實現(xiàn)
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、思路
定義一個小于數(shù)組長度增量，將整個數(shù)組中每隔一個增量的元素分為一組，對每組中的元素進行插入排序，再將增量減小，之后重復以上過程，直至增量減小為1時，對已經(jīng)進行過預(yù)處理的數(shù)組進行插入排序，達到減小復雜度的目的。
2、具體步驟
1.定義一個小于數(shù)組長度的增量gap（通常為數(shù)組長度的一半），將數(shù)組進行分組。
2.對每組中的元素進行插入排序的操作，使之有序。
3.減小增量gap（通常為減為一半），將數(shù)組再度細分。
4.重復2~3步驟，直至增量gap減小為1。
5.此時對整個數(shù)組再做插入排序操作，使整個數(shù)組有序。
3、代碼實現(xiàn)
void shellsort(int arr[], int len)
{
int gap=len; //定義增量
while(gap>1)
{
gap=gap/2; //將增量減小
int j;
for(j=0; j<len-gap; j++) //將數(shù)組分組
{
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}; //亂序數(shù)組
int len=sizeof(arr)/4;
int i;
for(i=0; i<len; i++)
{
printf("%d\t", arr[i]); //輸出初始數(shù)組，用于比較
}
putchar('\n');
selectsort(arr, len); //調(diào)用函數(shù)對數(shù)組進行排序，這里選用的是選擇排序的方式
for(i=0; i<len; i++)
{
printf("%d\t", arr[i]); //輸出排完序后的數(shù)組
}
putchar('\n');
return 0;
} 例題及其解答
題目描述
來源：?？途W(wǎng)
小明平時學習太用功了，閑暇時間就喜歡玩一種數(shù)字游戲，在這個游戲中，他每次會使用n個正整數(shù)先構(gòu)造一個數(shù)列（x1,……,xn），并可以根據(jù)需要無限次執(zhí)行以下操作：
選擇兩個不同的i，j，其中xi>xj，然后將xi改為xi-xj。
請你幫小明算一下，通過這樣的一系列操作，求出最終處理過數(shù)列的總和最小值是多少？
輸入描述
第一行一個整數(shù)n代表數(shù)列的長度，2<=n<=100，
第二行包含n個正整數(shù)x1 x2 x3 ... xi, 1<=xi<=100.
輸出描述
經(jīng)過多次操作后，數(shù)列總和的最小值（整數(shù)）。
示例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，經(jīng)過這兩步操作后，所有的數(shù)字都相等，因此操作不能再進行下去了，每個數(shù)都是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); //輸入數(shù)列長度
int arr[n]; //定義相應(yīng)長度的數(shù)組
int i;
for(i=0; i<n; i++)
{
scanf("%d", &arr[i]); //將輸入的數(shù)據(jù)存入數(shù)組
}
while(1)
{
sort(arr,n); //對數(shù)組進行排序
if(arr[0]==arr[n-1]) //判斷數(shù)組的首末元素是否相等
{
break; //若相等，則無法再進行作差操作
}
for(i=0;i<n-1; i++) //對數(shù)組中的相鄰且不相等的元素作差
{
if(arr[i]>arr[i+1])
{
arr[i]=arr[i]-arr[i+1];
}
}
}
int sum=0;
for(i=0; i<n; i++) //對最終的數(shù)組進行求和
{
sum=sum+arr[i];
}
printf("%d\n", sum); //輸出答案
return 0;
}結(jié)語
以上就是四種數(shù)組排序方式的全部內(nèi)容，以及在例題中的應(yīng)用。
到此這篇關(guān)于C語言中數(shù)組排序淺析的文章就介紹到這了,更多相關(guān)C語言數(shù)組排序內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
基于C++語言實現(xiàn)機動車違章處罰管理系統(tǒng)
這篇文章主要介紹了基于C++語言實現(xiàn)機動車違章處罰管理系統(tǒng)的相關(guān)資料,需要的朋友可以參考下2016-07-07
C/C++實現(xiàn)經(jīng)典象棋游戲的示例代碼
中國象棋是起源于中國的一種棋，屬于二人對抗性游戲的一種，在中國有著悠久的歷史。本文將利用C++實現(xiàn)這一經(jīng)典游戲，快跟隨小編一起學習一下吧2022-06-06
本文主要介紹了淺談QT打包的兩種方式，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2023-03-03
c++11之std::async 和std::thread的區(qū)別小結(jié)
std::async和std::thread都是C++11中提供的線程庫,它們都可以用于創(chuàng)建新線程,本文主要介紹了c++11之std::async 和std::thread的區(qū)別小結(jié),感興趣的可以了解一下2024-02-02
最近在做系統(tǒng)信息相關(guān)的接口,為了實現(xiàn)跨平臺,故在linux和Windows平臺獲取占用率信息,文章主要介紹Windows下的方法,文中給出了參考代碼,需要的朋友可以參考下2023-12-12
這篇文章主要為大家詳細介紹了C語言實現(xiàn)會員計費系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-05-05
這篇文章主要為大家介紹了Pthread?并發(fā)編程線程自底向上深入解析，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-11-11
C++中函數(shù)調(diào)用的方法與C語言并無區(qū)別,依舊是在調(diào)用方函數(shù)中執(zhí)行函數(shù)調(diào)用語句來實現(xiàn)函數(shù)調(diào)用,下面這篇文章主要給大家介紹了關(guān)于C++使用函數(shù)的一些高級操作,文中通過圖文介紹的非常詳細,需要的朋友可以參考下2022-12-12
C++使用opencv調(diào)用級聯(lián)分類器來識別目標物體的詳細流程
所謂級聯(lián)分類器其實就是把分類器按照一定的順序聯(lián)合到一起,下面這篇文章主要給大家介紹了關(guān)于C++使用opencv調(diào)用級聯(lián)分類器來識別目標物體的相關(guān)資料,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下2022-05-05
c語言中return與exit的區(qū)別淺析，需要的朋友可以參考一下2013-03-03