C語言面試常見考點排序總結
排序算法有兩塊比較重要的知識點
- 內存消耗 :算法的內存消耗可以通過空間復雜度來衡量,排序算法也不例外。不過,針對排序算法的空間復雜度,有一個概念是原地排序。原地排序算法是指空間復雜度是O(1)的排序算法。其中冒泡排序,插入排序、選擇排序都屬於原地排序算法
- 穩定性:針對排序算法,我們還有一個衡量指標是穩定性。這個概念是說,如果待排序的序列中存在值相等的元素,經過排序之後,相等元素之間原有的先後順序不變。
例如我們有一組數據 2 9 3 4 8 3 按照從小到大的排序是 2 3 3 4 8 9,經過某種排序算法之後,如果兩個3的前後順序沒有改變,就稱為穩定的排序算法,否則就是不穩定的排序算法
算法名稱 | 時間復雜度 | 是否穩定排序 | 是否原地排序 |
冒泡排序 | O(N^2) | 是 | 是 |
插入排序 | O(N^2) | 是 | 是 |
選擇排序 | O(N^2) | 否 | 是 |
歸並排序 | O(nlogn) | 是 | 否 |
快速排序 | O(nlogn) | 否 | 是 |
堆排序 | O(nlogn) | 是 | 是 |
冒泡排序
- 平均復雜度是O(N^2)
- 最好情況是O(1) 本身就是排好序的
- 最壞就是倒序O(N^2)
- 空間復雜度是O(1)
冒泡排序隻會操作相鄰的兩個數據。每次冒泡操作都會對相鄰的兩個元素進行比較,看是否滿足大小關系要求。如果不滿足就讓它倆互換。一次冒泡會讓至少一個元素移動到它應該在的位置,重復 n 次,就完成瞭 n 個數據的排序工作。
class Sort{ public: void MaoPao_Sort(vector<int> &arr){ //1.判斷溢出條件 if(arr.size() <2) return; int length =arr.size(); for(int i =0;i < length;i++){ for(int j=0; j < length -i -1 ;j++){ if(arr[j] >arr[j+1]){ int temp = arr[j]; arr[j]= arr[j+1]; arr[j+1]=temp; } } } } };
插入排序
插入排序思想的由來,其實就是按照在一個有序的數組中插入一個元素的思想,找到合適的位置進行插入並遷移後面的元素
首先,我們將數組中的數據分為兩個區間,已排序區間和未排序區間。初始已排序區間隻有一個元素,就是數組的第一個元素。插入算法的核心思想是取未排序區間中的元素,在已排序區間中找到合適的插入位置將其插入,並保證已排序區間數據一直有序。重復這個過程,直到未排序區間中元素為空,算法結束。
class Sort{ public: void Insert_Sort(vector<int> &arr){ //1.判斷溢出條件 if(arr.size() < 2) return; int length =arr.size(); int j =0;//初始的已排序區間的下標 for(int i =1;i < length ;i++){ //從未排序的區間裡面取元素 int temp =arr[i]; j =i-1; //不斷更新已排序區間 while(j >= 0 && temp <a[j]){ //如果小的話就往後移動,找到合適的插入位置 arr[j+1]=arr[j]; j--; } arr[j+1]=temp; //插入元素 } } };
選擇排序
選擇排序算法的實現思路有點類似插入排序,也分已排序區間和未排序區間。但是選擇排序每次會從未排序區間中找到最小的元素,將其放到已排序區間的末尾
class Sort{ public: void Select_Sort(vector<int> &arr ,int length){ for(int i =0;i < length -1;i++){ int min_number =arr[i]; int flag = i; for(int j =i;j <length ;j++){ if(min_number > arr[j]){ min_number = arr[j]; flag =j; } } //交換數字 arr[flag] =arr[i]; arr[i]=min_number; } } };
歸並排序
歸並排序是由下而上,采用分治的思想,把數據先拆分在合並,並把合並後的數據存入臨時數組中,保證原先的數據位置不發生變化,是一種穩定的排序但不是原地排序,時間復雜度是O(nlogn),空間復雜度是O(N)
class Sort{ public: //歸並排序 void MergeSort(vector<int> & arr){ if(arr.size() < 2){ return ; } //拆分函數 Merge_Process(arr,0,arr.size())-1); } //先拆分,這是拆分函數 void Merge_Process(vector<int> &arr,int start,int end){ //遞歸拆分,首先需要遞歸的終止條件 if(end -start == 0) return; int mid =((end -start)/2) +start; Merge_Process(arr,start,mid); Merge_Process(arr,mid+1,end); //在合並 Merge(arr,start,mid,end); } //合並函數 void Merge(vector<int> &arr,int start,int mid, int end){ vector<int> temp(end-start+1,0);//初始化一個臨時數組 int tempIndex =0; //輔助空間索引 int leftIndex =start; int rightIndex =mid+1; while(leftIndex <= mid && rightIndex <= end){ if(leftIndex <rightIndex){ temp[tempIndex++] =arr[leftIndex++]; }else{ temp[tempIndex++] =arr[rightIndex++]; } } while(leftIndex <= mid){ temp[tempIndex++]=arr[leftIndex++]; } while(rightIndex <= end){ temp[tempIndex++]=arr[rightIndex++]; } for(int i =0;i< temp.size();i++){ arr[start+i]=temp[i]; } } };
快速排序
快速排序是先分區,在處理子問題,通過找到區間後取得任意一個分區點,小的放分區點左邊,大的放分區點右邊,時間復雜度是O(nlong),空間復雜度是O(1),是原地排序但不是穩定排序
快排優化的話,有:三數取中法,和隨機法,都是為瞭防止要排序的數組中有重復元素,這塊我演示的是隨機法
class Sort{ public: void quickSort(vector<int> &arr,int begin, int low){ if(begin <end){ //產生一個隨機值 int index =rand()%(end-begin+1)+begin; //然後把產生的這個隨機值,替換到數組的首位 swap(arr[begin],arr[index]); int i =begin; int j =end; int base =arr[i];//基準位 while(i <j){ while(i<j&& arr[j] >= base){ j--; } num[i]=num[j]; while(i<j && arr[i] < base){ i++; } num[j]=num[i]; } //回歸基準位 num[i]=base; //遞歸開始處理子問題 quickSort(arr,begin,i-1); quickSort(arr,i+1,end); } } };
以上就是C語言面試常見考點排序總結的詳細內容,更多關於C語言 排序的資料請關註WalkonNet其它相關文章!