<em>Mac</em>Book项目 2009年学校开始实施<em>Mac</em>Book项目,所有师生配备一本<em>Mac</em>Book,并同步更新了校园无线网络。学校每周进行电脑技术更新,每月发送技术支持资料,极大改变了教学及学习方式。因此2011
2021-06-01 09:32:01
本文介紹了幾種c語言中對亂序陣列的排序方式。
具體的內容有:
具體內容詳見下文。
首先假設陣列的的前n位元素是有序的,然後從第n+1位開始,將此元素插入到前面,使得前n+1位元素有序,以此類推,直至整個陣列有序。
在對第n+1位元素操作時,使用臨時變數存放該元素的值,從第n位元素開始向前比較,同時將與其比較的元素向後移動,直到與其比較的元素比其小時,將臨時變數中的值放入該元素後的一個陣列元素中。
1.從第一個元素開始,該元素可以認為已經被排序。
2.取下一個元素存入臨時變數temp,對前方有序序列從後往前掃描。
3.如果該元素大於temp,則將該元素移到下一位。
4.重複步驟3,直到找到已於等於temp的元素。
5.temp插入到該元素的後面一位,如果所有有序元素都大於temp,則將temp插入到下標為0的位置(既陣列的首位,說明該元素是目前最小的元素)。
6.重複以上的2~5步驟,直至操作完整個陣列中的所有元素。
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變數插入有序部分 } }
時間複雜度: O(N)~O(N^2)
空間複雜度:O(1)
通過對陣列內相鄰元素的比較,使較大的元素向後移動,較小的元素向前移動,不斷迴圈此過程,直至整個陣列有序。
當第n次迴圈結束後,陣列的最後n位為有序,所以每回圈一次,就可以將回圈的範圍(後界)向前減少一位元素。
1.將陣列中的第一個元素與下一個元素進行比較,若第一個元素較大,則交換位置。
2.繼續比較下兩個元素的大小,將較大的元素放在靠後的位置。
3.重複步驟2,直至完成第n-1個元素與第n個元素的比較。
4.將回圈的後界減一,重複1~5步驟。
5.當迴圈的範圍減為1時,此時的為有序陣列。
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; } } } }
時間複雜度: O(N)~O(N^2)
空間複雜度: O(1)
不斷掃描陣列,每次選出一個最小值和一個最大值,分別放在序列的首位置和末位置,然後將序列的首位置與末位置分別向後與前移動一位。直至排完整個陣列。
1.定義序列的首末位置。
2.掃描首末位置之間的序列,選出一個最小值min和一個最大值max,記錄下標值。
3.將最小值放入首位置start,最大值放入末位置end。
4.將首位置向後移動一位,末位置向前移動一位。
5.重複2~4步驟,直至首末位置重合(start>=end),此時的陣列為有序陣列。
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--; //末位置前移一位 } }
時間複雜度: O(N^2)
空間複雜度: O(1)
定義一個小於陣列長度增量,將整個陣列中每隔一個增量的元素分為一組,對每組中的元素進行插入排序,再將增量減小,之後重複以上過程,直至增量減小為1時,對已經進行過預處理的陣列進行插入排序,達到減小複雜度的目的。
1.定義一個小於陣列長度的增量gap(通常為陣列長度的一半),將陣列進行分組。
2.對每組中的元素進行插入排序的操作,使之有序。
3.減小增量gap(通常為減為一半),將陣列再度細分。
4.重複2~3步驟,直至增量gap減小為1。
5.此時對整個陣列再做插入排序操作,使整個陣列有序。
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; } } }
時間複雜度: 平均 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.
經過多次操作後,數列總和的最小值(整數)。
輸入
5
45 12 27 30 18
輸出
15
輸入
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!
相關文章
<em>Mac</em>Book项目 2009年学校开始实施<em>Mac</em>Book项目,所有师生配备一本<em>Mac</em>Book,并同步更新了校园无线网络。学校每周进行电脑技术更新,每月发送技术支持资料,极大改变了教学及学习方式。因此2011
2021-06-01 09:32:01
综合看Anker超能充系列的性价比很高,并且与不仅和iPhone12/苹果<em>Mac</em>Book很配,而且适合多设备充电需求的日常使用或差旅场景,不管是安卓还是Switch同样也能用得上它,希望这次分享能给准备购入充电器的小伙伴们有所
2021-06-01 09:31:42
除了L4WUDU与吴亦凡已经多次共事,成为了明面上的厂牌成员,吴亦凡还曾带领20XXCLUB全队参加2020年的一场音乐节,这也是20XXCLUB首次全员合照,王嗣尧Turbo、陈彦希Regi、<em>Mac</em> Ova Seas、林渝植等人全部出场。然而让
2021-06-01 09:31:34
目前应用IPFS的机构:1 谷歌<em>浏览器</em>支持IPFS分布式协议 2 万维网 (历史档案博物馆)数据库 3 火狐<em>浏览器</em>支持 IPFS分布式协议 4 EOS 等数字货币数据存储 5 美国国会图书馆,历史资料永久保存在 IPFS 6 加
2021-06-01 09:31:24
开拓者的车机是兼容苹果和<em>安卓</em>,虽然我不怎么用,但确实兼顾了我家人的很多需求:副驾的门板还配有解锁开关,有的时候老婆开车,下车的时候偶尔会忘记解锁,我在副驾驶可以自己开门:第二排设计很好,不仅配置了一个很大的
2021-06-01 09:30:48
不仅是<em>安卓</em>手机,苹果手机的降价力度也是前所未有了,iPhone12也“跳水价”了,发布价是6799元,如今已经跌至5308元,降价幅度超过1400元,最新定价确认了。iPhone12是苹果首款5G手机,同时也是全球首款5nm芯片的智能机,它
2021-06-01 09:30:45