網站首頁 編程語言 正文
前言
本文介紹了幾種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("%d\t", arr[i]); //輸出初始數組，用于比較
}
putchar('\n');
selectsort(arr, len); //調用函數對數組進行排序，這里選用的是選擇排序的方式
for(i=0; i<len; i++)
{
printf("%d\t", 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("%d\n", sum); //輸出答案
return 0;
}結語
以上就是四種數組排序方式的全部內容，以及在例題中的應用。
原文鏈接：https://blog.csdn.net/wsbydmm/article/details/127854726
相關推薦
- 2022-09-20 Springboot整合Redis與數據持久化_Redis
- 2022-09-13 Android?Studio實現簡單補間動畫_Android
- 2023-07-02 oracle數據庫排序后如何獲取第一條數據_oracle
- 2022-11-25 詳解React中Fragment的簡單使用_React
- 2022-10-11 Windows下vs中對DLL、exe文件添加屬性信息
- 2022-10-04 淺析C++模板類型中的原樣轉發和可變參數的實現_C 語言
- 2022-12-29 Python?Base64編碼和解碼操作_python
- 2022-07-11 Sonatype Nexus搭建Maven私服
- 最近更新
-
- window11 系統安裝 yarn
- 超詳細win安裝深度學習環境2025年最新版（
- Linux 中運行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎操作-- 運算符，流程控制 Flo
- 1. Int 和Integer 的區別，Jav
- spring @retryable不生效的一種
- Spring Security之認證信息的處理
- Spring Security之認證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權
- redisson分布式鎖中waittime的設
- maven:解決release錯誤：Artif
- restTemplate使用總結
- Spring Security之安全異常處理
- MybatisPlus優雅實現加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務發現-Nac
- Spring Security之基于HttpR
- Redis 底層數據結構-簡單動態字符串（SD
- arthas操作spring被代理目標對象命令
- Spring中的單例模式應用詳解
- 聊聊消息隊列，發送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠程分支
提供CDN加速