本篇先上五種常用排序
分別是 冒泡排序、選擇排序、直接插入排序、希爾排序、快速排序? 五種
冒泡排序(bubbleSort)
冒泡排序是最常用最簡單的排序,以親民的代碼,簡單的思路廣受碼農(nóng)的喜愛
????????冒泡排序是一種簡單的排序算法,它重復地遍歷要排序的數(shù)列,一次比較兩個元素,如果它們的順序錯誤就把它們交換過來。重復地進行這個過程直到整個數(shù)列都有序。冒泡排序的時間復雜度為O(n^2),因此對于大規(guī)模數(shù)據(jù)排序時效率較低,但對于小規(guī)模數(shù)據(jù)排序是一種簡單且實用的排序算法。
此為一個arr[5]數(shù)組的排序過程,黑色為未排序,綠色未已完成排序,每次比較兩個元素。
代碼極為簡單
void bubbleSort(int arr[], int n) {
int i, j;
// 外層循環(huán)控制排序輪數(shù),每輪確定一個最大值
for (i = 0; i < n-1; i++) {
// 內(nèi)層循環(huán)控制每輪比較次數(shù),每次確定一個最大值
for (j = 0; j < n-i-1; j++) {
// 如果前一個數(shù)比后一個數(shù)大,就交換它們的位置
if (arr[j] > arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
如何學習冒泡排序
1. 了解冒泡排序的基本原理和算法流程;
2. 掌握冒泡排序的時間復雜度和空間復雜度;
3. 熟悉冒泡排序的代碼實現(xiàn);
4. 進行冒泡排序的練習和實踐;
5. 總結(jié)冒泡排序的優(yōu)缺點和適用場景。
選擇排序(selectionSort)
????????選擇排序是一種簡單的排序算法,它的基本思想是每次從待排序的數(shù)據(jù)元素中選出最小(或最大)的一個元素,存放在序列的起始位置,直到全部待排序的數(shù)據(jù)元素排完。選擇排序的時間復雜度為O(n^2),因此對于大規(guī)模數(shù)據(jù)排序時效率較低,但對于小規(guī)模數(shù)據(jù)排序是一種簡單且實用的排序算法。
選擇排序的算法流程如下:
1. 初始狀態(tài):無序區(qū)為R[1..n],有序區(qū)為空;
2. 第i趟排序(i=1,2,3…n-1)開始時,當前有序區(qū)和無序區(qū)分別為R[1..i-1]和R(i..n)。該趟排序從當前無序區(qū)中-選出關鍵字最小的記錄 R[k],將它與無序區(qū)的第1個記錄R交換,使R[1..i]和R[i+1..n)分別變?yōu)橛涗泜€數(shù)增加1個的新有序區(qū)和記錄個數(shù)減少1個的新無序區(qū);
3. n-1趟結(jié)束,數(shù)組有序化了。
講一下無序區(qū)和有序區(qū)是什么意思
????????冒泡排序、選擇排序和直接插入排序都是基于比較的排序算法,它們的基本思想都是將待排序的數(shù)據(jù)元素分成有序區(qū)和無序區(qū),每次從無序區(qū)中選出一個元素,將它插入到有序區(qū)中的合適位置,從而逐漸將無序區(qū)中的元素插入到有序區(qū)中,最終得到一個有序的序列。
????????在冒泡排序和選擇排序中,有序區(qū)和無序區(qū)的劃分是通過排序輪數(shù)來實現(xiàn)的。每輪排序后,無序區(qū)的元素個數(shù)減少1個,有序區(qū)的元素個數(shù)增加1個,直到整個序列有序。
????????在直接插入排序中,有序區(qū)和無序區(qū)的劃分是通過插入元素的位置來實現(xiàn)的。初始時,整個序列都是無序區(qū),每次將無序區(qū)的第一個元素插入到有序區(qū)的合適位置,從而逐漸將無序區(qū)中的元素插入到有序區(qū)中,最終得到一個有序的序列。
????????因此,無序區(qū)就是待排序的數(shù)據(jù)元素中還沒有被插入到有序區(qū)中的元素,有序區(qū)就是已經(jīng)排好序的數(shù)據(jù)元素。
選擇排序的代碼實現(xiàn)如下:
void selectionSort(int arr[], int n) {
int i, j, min;
// 外層循環(huán)控制排序輪數(shù),每輪確定一個最小值
for (i = 0; i < n-1; i++) {
// 假設當前輪數(shù)的第一個元素為最小值
min = i;
// 內(nèi)層循環(huán)控制每輪到最小值的下標
for (j = i+1; j < n; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
// 將最小值與當前輪數(shù)的第一個元素交換位置
int temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
}
怎樣學習選擇排序
1. 了解選擇排序的基本原理和算法流程;
2. 掌握選擇排序的時間復雜度和空間復雜度;
3. 熟悉選擇排序的代碼實現(xiàn);
4. 進行選擇排序的練習和實踐;
5. 總結(jié)選擇排序的優(yōu)缺點和適用場景。
? ? ? ? ?此為一個arr[5]數(shù)組進行的選擇排序
選擇排序的優(yōu)缺點和適用場景:
優(yōu)點:
1. 簡單,容易實現(xiàn);
2. 不占用額外的內(nèi)存空間。
缺點:
1. 時間復雜度為O(n^2),效率較低;
2. 不穩(wěn)定,可能會改變項。
適用場景:
????????選擇排序適用于數(shù)據(jù)規(guī)模較小的情況,因為它的時間復雜度為O(n^2),對于大規(guī)模數(shù)據(jù)排序時效率較低。但是,選擇排序不需要額外的內(nèi)存空間,因此在空間有限的情況下,選擇排序是一種簡單且實用的排序算法。
直接插入排序(insertionSort)
????????直接插入排序是一種簡單的排序算法,它的基本思想是將待排序的數(shù)據(jù)元素插入到已經(jīng)有序的序列中,從而得到一個新的、個數(shù)加一的有序序列。直接插入排序的時間復雜度為O(n^2),因此對于大規(guī)模數(shù)據(jù)排序時效率較低,但對于小規(guī)模數(shù)據(jù)排序是一種簡單且實用的排序算法。
? ? ? ? ? ? ? ? 此為一個arr[5]數(shù)組進行的直接插入排序
直接插入排序的算法流程如下:
1. 初始狀態(tài):無序區(qū)為R[1..n],有序區(qū)為空;
2. 第i趟排序(i=1,2,3…n-1)開始時,當前有序區(qū)和無序區(qū)分別為R[1..i-1]和R(i..n)。該趟排序從當前無序區(qū)中-取出第一個元素R[i],將它插入到有序區(qū)的合適位置,使R[1..i]和R[i+1..n)分別變?yōu)橛涗泜€數(shù)增加1個的新有序區(qū)和記錄個數(shù)減少1個的新無序區(qū);
3. n-1趟結(jié)束,數(shù)組有序化了。
直接插入排序的代碼實現(xiàn)如下:
void insertSort(int arr[],int len){
int i,j,temp;
for(i=1;i<len;i++){ //從1開始,0位置當成有序
temp=arr[i]; //temp記錄未排序第一個
for(j=i-1;j>=0&&arr[j]>temp;j--){
arr[j+1]=arr[j]; //元素后移,騰位置給插入元素
}
arr[j+1]=temp; //插入 比較的 后一位
}
}
怎樣學習直接插入排序:
1. 了解直接插入排序的基本原理和算法流程;
2. 掌握直接插入排序的時間復雜度和空間復雜度;
3. 熟悉直接插入排序的代碼實現(xiàn);
4. 進行直接插入排序的練習和實踐;
5. 總結(jié)直接插入排序的優(yōu)缺點和適用場景。
6. 了解直接插入排序的優(yōu)化算法,如希爾排序;
直接插入排序的優(yōu)缺點和適用場景:
優(yōu)點:
1. 簡單,容易實現(xiàn);
2. 穩(wěn)定,不會改變相同元素的相對位置;
3. 對于小規(guī)模數(shù)據(jù)排序時效率較高。
缺點:
1. 時間復雜度為O(n^2),效率較低;
2. 對于大規(guī)模數(shù)據(jù)排序時效率較低。
適用場景:
????????直接插入排序適用于數(shù)據(jù)規(guī)模較小的情況,因為它的時間復雜度為O(n^2),對于大規(guī)模數(shù)據(jù)排序時效率較低。但是,直接插入排序是一種穩(wěn)定的排序算法,不會改變相同元素的相對位置,因此在需要保持相同元素相對位置的情況下,直接插入排序是一種簡單且實用的排序算法。
希爾排序(shellSort)
????????希爾排序是直接插入排序的改進版,它通過將待排序的數(shù)據(jù)元素分組,對每組進行直接插入排序,從而使得整個序列逐步變得有序。希爾排序的時間復雜度為O(nlogn),比直接插入排序的時間復雜度O(n^2)要低,因此對于大規(guī)模數(shù)據(jù)排序時效率更高。此外,希爾排序也是一種穩(wěn)定的排序算法,不會改變相同元素的相對位置。因此,在需要保持相同元素相對位置的情況下,希爾排序是一種更好的選擇。? ?(這也是希爾排序相比直接插入排序的優(yōu)點與選擇)
希爾排序的算法流程如下:
1. 選擇一個增量序列t1,t2,…,tk,其中ti>tj,tk=1;
2. 按增量序列個數(shù)k,對序列進行k趟排序;
3. 每趟排序,根據(jù)對應的增量dk,將待排序列分割成若干長度為m的子序列,分別對各子表進行直接插入排序。僅增量因子為1時,整個序列作為一個表來處理,表長度即為整個序列的長度。
? ? ? ? ? ? ? ? 這是增量dk為2的arr[6]數(shù)組的第一次排序過程
希爾排序的代碼實現(xiàn)如下:
//dk 是增量 步長
void shellInsert(int arr[],int len,int dk){
int i,j,temp;
for(i=dk;i<len;i++){
//判斷每組的 第幾個元素大小
if(arr[i]<arr[i-dk]){ //后邊組小于前邊組
temp=arr[i];
j=i-dk;
for(;j>=0&&temp<arr[j];j=j-dk){
//前面的值 給到 后面
arr[j+dk]=arr[j];
}
arr[j+dk]=temp;
}
}
怎樣學習希爾排序
1. 了解希爾排序的基本原理和算法流程;
2. 掌握希爾排序的時間復雜度和空間復雜度;
3. 熟悉希爾排序的代碼實現(xiàn);
4. 進行希爾排序的練習和實踐;
5. 總結(jié)希爾排序的優(yōu)缺點和適用場景;
6. 了解希爾排序的優(yōu)化算法,如快速排序、歸并排序等;
7. 進一步學習其他排序算法,如堆排序、計數(shù)排序、桶排序等。
希爾排序的優(yōu)缺點和適用場景:
優(yōu)點:
1. 時間復雜度為O(nlogn),比直接插入排序的時間復雜度O(n^2)要低,對于大規(guī)模數(shù)據(jù)排序時效率更高;
2. 穩(wěn)定,不會改變相同元素的相對位置。
缺點:
1. 實現(xiàn)較為復雜;
2. 不同的增量序列會影響排序效率。
適用場景:
????????希爾排序適用于數(shù)據(jù)規(guī)模較大的情況,因為它的時間復雜度為O(nlogn),對于大規(guī)模數(shù)據(jù)排序時效率更高。此外,希爾排序也是一種穩(wěn)定的排序算法,不會改變相同元素的相對位置。但是,希爾排序的實現(xiàn)較為復雜,需要選擇合適的增量序列才能達到較好的排序效果。因此,在需要對大規(guī)模數(shù)據(jù)進行排序且不需要保持相同元素相對位置的情況下,希爾排序是一種較好的選擇。
快速排序
????????快速排序是一種高效的排序算法,它的基本思想是通過一趟排序?qū)⒋判虻臄?shù)據(jù)分割成獨立的兩部分,其中一部分的所有數(shù)據(jù)都比另一部分的所有數(shù)據(jù)小,然后再按照此方法對這兩部分數(shù)據(jù)分別進行快速排序,整個排序過程可以遞歸進行,以此達到整個序列有序的目的??焖倥判虻臅r間復雜度為O(nlogn),是一種效率較高的排序算法。
快速排序的算法流程如下:
1. 選擇一個基準元素,通常選擇第一個元素或最后一個元素。
2. 將待排序序列分成兩部分,一部分所有元素都比基準元素小,另一部分所有元素都比基準元素大。
3. 對兩部分分別進行快速排序,遞歸進行,直到序列有序。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 通過基準值分成兩部分
快速排序的代碼實現(xiàn)如下:
int getPivot(int arr[],int low,int high){
int pivot=arr[low];
while(low<high){ //i<j的時候
//j從后向前找比基準值小的元素f
while(low<high&&arr[high]>=pivot){
high--;
}
//找到了比基準值小的元素 將元素給到i位置
arr[low]=arr[high];
//i從前往后找比基準值大的元素
while(low<high&&arr[low]<=pivot){
low++;
}
arr[high]=arr[low];
}
//結(jié)束條件 i=j 找到了基準值的位置
arr[low]=pivot;
//返回基準值位置
return low;
}
void quickSort(int arr[],int low,int high){
if(low<high){
//基準值位置的變量
int pivot=getPivot(arr,low,high);
//遞歸對基準值位置左邊進行快速排序
quickSort(arr,low,pivot-1);
//遞歸對基準值位置右邊進行快速排序
quickSort(arr,pivot+1,high);
}
}
怎樣學習快速排序
1. 了解快速排序的基本原理和算法流程;
2. 掌握快速排序的時間復雜度和空間復雜度;
3. 熟悉快速排序的代碼實現(xiàn);
4. 進行快速排序的練習和實踐;
5. 總結(jié)快速排序的優(yōu)缺點和適用場景;
6. 了解快速排序的優(yōu)化算法,如三路快排、隨機化快排等;
7. 進一步學習其他排序算法,如歸并排序、堆排序等。
快速排序的優(yōu)缺點和適用場景:
優(yōu)點:
1. 時間復雜度為O(nlogn),比直接插入排序的時間復雜度O(n^2)要低,對于大規(guī)模數(shù)據(jù)排序時效率更高;
2. 穩(wěn)定,不會改變相同元素的相對位置。
缺點:
1. 實現(xiàn)較為復雜;
2. 不同的增量序列會影響排序效率。
適用場景:
????????希爾排序適用于數(shù)據(jù)規(guī)模較大的情況,因為它的時間復雜度為O(nlogn),對于大規(guī)模數(shù)據(jù)排序時效率更高。此外,希爾排序也是一種穩(wěn)定的排序算法,不會改變相同元素的相對位置。但是,希爾排序的實現(xiàn)較為復雜,需要選擇合適的增量序列才能達到較好的排序效果。因此,在需要對大規(guī)模數(shù)據(jù)進行排序且不需要保持相同元素相對位置的情況下,希爾排序是一種較好的選擇。
本篇先上三種常用查找
分別是 順序查找、二分查找、分塊查找 三種
順序查找
????????順序查找,也稱線性查找,是一種簡單的查找算法,它的基本思想是從待查找的數(shù)據(jù)元素序列的第一個元素開始,依次比較每個元素,直到找到目標元素或查找完整個序列為止。順序查找的時間復雜度為O(n),因此對于大規(guī)模數(shù)據(jù)查找時效率較低,但對于小規(guī)模數(shù)據(jù)查找是一種簡單且實用的查找算法。
順序查找的算法流程如下:
1. 從待查找的數(shù)據(jù)元素序列的第一個元素開始;
2. 依次比較每個元素,直到找到目標元素或查找完整個序列為止。
順序查找的代碼實現(xiàn)如下:
int sequentialSearch(int arr[], int n, int target) {
? ? int i;
? ? for (i = 0; i < n; i++) {
? ? ? ? if (arr[i] == target) {
? ? ? ? ? ? return i;
? ? ? ? }
? ? }
? ? return -1;//找不到
}
順序查找的優(yōu)缺點和適用場景:
優(yōu)點:
1. 簡單,容易實現(xiàn);
2. 對于小規(guī)模數(shù)據(jù)查找時效率較高。
缺點:
1. 時間復雜度為O(n),效率較低;
2. 不適用于大規(guī)模數(shù)據(jù)查找。
適用場景:
????????順序查找適用于數(shù)據(jù)規(guī)模較小的情況,因為它的時間復雜度為O(n),對于大規(guī)模數(shù)據(jù)查找時效率較低。但是,順序查找是一種簡單且實用的查找算法,對于小規(guī)模數(shù)據(jù)查找是一種較好的選擇。在需要對大規(guī)模數(shù)據(jù)進行查找時,可以考慮使用其他更高效的查找算法,如二分查找、哈希查找等。
二分查找
????????二分查找,也稱折半查找,是一種高效的查找算法,它的基本思想是將待查找的數(shù)據(jù)元素序列分成兩部分,取中間位置的元素進行比較,如果中間位置的元素等于目標元素,則查找成功;如果中間位置的元素大于目標元素,則在左半部分繼續(xù)查找;如果中間位置的元素小于目標元素,則在右半部分繼續(xù)查找。通過不斷縮小查找范圍,最終可以找到目標元素或確定目標元素不存在。二分查找的時間復雜度為O(logn),是一種效率較高的查找算法。
二分查找的算法流程如下:
1. 將待查找的數(shù)據(jù)元素序列按照大小順序排列;
2. 取中間位置的元素進行比較,如果中間位置的元素等于目標元素,則查找成功;
3. 如果中間位置的元素大于目標元素,則在左半部分繼續(xù)查找;
4. 如果中間位置的元素小于目標元素,則在右半部分繼續(xù)查找;
5. 重復步驟2~4,直到找到目標元素或確定目標元素不存在。
如何學習二分查找
1. 了解二分查找的基本原理和算法流程;
2. 掌握二分查找的時間復雜度和空間復雜度;
3. 熟悉二分查找的代碼實現(xiàn);
4. 進行二分查找的練習和實踐;
5. 總結(jié)二分查找的優(yōu)缺點和適用場景;
6. 了解二分查找的變體算法,如插值查找、斐波那契查找等;
7. 進一步學習其他查找算法,如哈希查找、線性查找等。
二分查找分為遞歸和非遞歸兩種。
二分查找遞歸和非遞歸的區(qū)別
????????二分查找的遞歸實現(xiàn)和非遞歸實現(xiàn)的區(qū)別在于遞歸實現(xiàn)使用函數(shù)調(diào)用棧來保存中間結(jié)果,而非遞歸實現(xiàn)使用循環(huán)來實現(xiàn)。遞歸實現(xiàn)的代碼相對簡潔,但是由于需要使用函數(shù)調(diào)用棧,可能會導致棧溢出的問題;非遞歸實現(xiàn)的代碼相對復雜,但是由于不需要使用函數(shù)調(diào)用棧,可以避免棧溢出的問題。在實際應用中,可以根據(jù)具體情況選擇遞歸實現(xiàn)或非遞歸實現(xiàn)。
二分查找的遞歸代碼實現(xiàn):
int binarySearch(int arr[],int low,int high,int key){
int mid; //中間下標
while(low<=high){
mid=(high+low)/2;
if(key==arr[mid]){
return mid; //遞歸出口
}
else if(key>arr[mid]){
return binarySearch(arr,mid+1,high,key);
}
else{
return binarySearch(arr,low,mid-1,key);
}
}
return -1;
}
二分查找的遞歸代碼實現(xiàn):
//arr 數(shù)組 low 左邊值 high 右邊值 key 要查找的關鍵字
int binarySearch(int arr[],int low,int high,int key){
int mid; //中間值
while(low<=high){
mid=(low+high)/2; //找中間位置
if(key==arr[mid]){
return mid; //返回下標
}
else if(key>arr[mid]){
low=mid+1u
}
else{
high=mid-1;
}
}
//沒有找到關鍵字
return -1;
}
二分查找的優(yōu)缺點和適用場景:
優(yōu)點:
1. 時間復雜度為O(logn),效率較高;
2. 對于有序數(shù)據(jù)元素序列查找時效率較高。
缺點:
1. 只適用于有序數(shù)據(jù)元素序列查找;
2. 數(shù)據(jù)元素序列變化較大時,需要重新排序。
適用場景:
????????二分查找適用于有序數(shù)據(jù)元素序列查找的情況,因為它的時間復雜度為O(logn),對于有序數(shù)據(jù)元素序列查找時效率較高。但是,二分查找只適用于有序數(shù)據(jù)元素序列查找,如果數(shù)據(jù)元素序列變化較大時,需要重新排序。因此,在需要對有序數(shù)據(jù)元素序列進行查找時,二分查找是一種較好的選擇。在需要對無序數(shù)據(jù)元素序列進行查找時,可以考慮使用其他更高效的查找算法,如哈希查找、線性查找等。
分塊查找
????????分塊查找,也稱塊查找,是一種基于分塊思想的查找算法,它的基本思想是將待查找的數(shù)據(jù)元素序列分成若干塊,每塊中的數(shù)據(jù)元素可以是無序的,但塊與塊之間必須是有序的。然后,通過對塊的查找和定位,縮小查找范圍,最終在對應的塊中進行順序查找,從而找到目標元素。分塊查找的時間復雜度為O(sqrt(n)),是一種效率較高的查找算法。
分塊查找的算法流程如下:
1. 將待查找的數(shù)據(jù)元素序列分成若干塊,每塊中的數(shù)據(jù)元素可以是無序的,但塊與塊之間必須是有序的;
2. 對每個塊進行查找和定位,縮小查找范圍;
3. 在對應的塊中進行順序查找,從而找到目標元素。
分塊查找的代碼實現(xiàn)如下:
// 分塊查找
int blockSearch(int arr[], int n, int m, int target) {
? ? int blockSize = sqrt(n); // 每塊的大小
? ? int blockIndex = m / blockSize; // 目標元素所在塊的索引
? ? int left = blockIndex * blockSize; // 目標元素所在塊的左邊界
? ? int right = (blockIndex + 1) * blockSize - 1; // 目標元素所在塊的右邊界
? ? if (right >= n) { // 如果右邊界超出數(shù)組范圍,則將其設置為數(shù)組最后一個元素的索引
? ? ? ? right = n - 1;
? ? }
? ? for (int i = left; i <= right; i++) { // 在目標元素所在塊中進行順序查找
? ? ? ? if (arr[i] == target) {
? ? ? ? ? ? return i;
? ? ? ? }
? ? }
? ? return -1; // 如果未找到目標元素,則返回-1
}
如何學習分塊查找
1. 了解分塊查找的基本原理和算法流程;
2. 掌握分塊查找的時間復雜度和空間復雜度;
3. 熟悉分塊查找的代碼實現(xiàn);
4. 進行分塊查找的練習和實踐;
5. 總結(jié)分塊查找的優(yōu)缺點和適用場景;
6. 了解分塊查找的變體算法,如B+樹、B樹等;
7. 進一步學習其他查找算法,如二分查找、哈希查找等。
?
分塊查找的優(yōu)缺點和適用場景:
優(yōu)點:
1. 時間復雜度為O(sqrt(n)),效率較高;
2. 對于大規(guī)模數(shù)據(jù)查找時效率較高。
缺點:
1. 實現(xiàn)較為復雜;
2. 對于數(shù)據(jù)元素序列變化較大的情況,需要重新構建塊。
適用場景:
????????分塊查找適用于大規(guī)模數(shù)據(jù)查找的情況,因為它的時間復雜度為O(sqrt(n)),對于大規(guī)模數(shù)據(jù)查找時效率較高。此外,分塊查找也適用于數(shù)據(jù)元素序列變化較小的情況,因為只需要對塊進行重新構建即可。但是,分塊查找的實現(xiàn)較為復雜,需要對數(shù)據(jù)元素序列進行分塊和排序,因此在需要對小規(guī)模數(shù)據(jù)進行查找時,可以考慮使用其他更簡單的查找算法,如順序查找、二分查找等。在需要對大規(guī)模數(shù)據(jù)進行查找時,分塊查找是一種較好的選擇。文章來源:http://www.zghlxwxcb.cn/news/detail-763823.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-763823.html
到了這里,關于【C語言入門】五種排序,三種查找(配圖新手向)的文章就介紹完了。如果您還想了解更多內(nèi)容,請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章,希望大家以后多多支持TOY模板網(wǎng)!