C語言面試常見考點排序總結

更新時間：2021年11月23日 10:53:40 作者：悟道xn

深處開發(fā)崗，其實排序也是繞不開的環(huán)節(jié)，其中冒泡排序，選擇排序，插入排序，歸并排序，快速排序，堆排序也是我在秋招以來頻繁問到的技術點，今天我們來重點聊聊排序

排序算法有兩塊比較重要的知識點

內存消耗：算法的內存消耗可以通過空間復雜度來衡量，排序算法也不例外。不過，針對排序算法的空間復雜度，有一個概念是原地排序。原地排序算法是指空間復雜度是O(1)的排序算法。其中冒泡排序，插入排序、選擇排序都屬于原地排序算法
穩(wěn)定性：針對排序算法，我們還有一個衡量指標是穩(wěn)定性。這個概念是說，如果待排序的序列中存在值相等的元素，經過排序之后，相等元素之間原有的先后順序不變。

例如我們有一組數據 2 9 3 4 8 3 按照從小到大的排序是 2 3 3 4 8 9，經過某種排序算法之后，如果兩個3的前后順序沒有改變，就稱為穩(wěn)定的排序算法，否則就是不穩(wěn)定的排序算法

算法名稱	時間復雜度	是否穩(wěn)定排序	是否原地排序
冒泡排序	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;
				}
			}
		}
	}		
};

插入排序

插入排序思想的由來，其實就是按照在一個有序的數組中插入一個元素的思想，找到合適的位置進行插入并遷移后面的元素

首先，我們將數組中的數據分為兩個區(qū)間，已排序區(qū)間和未排序區(qū)間。初始已排序區(qū)間只有一個元素，就是數組的第一個元素。插入算法的核心思想是取未排序區(qū)間中的元素，在已排序區(qū)間中找到合適的插入位置將其插入，并保證已排序區(qū)間數據一直有序。重復這個過程，直到未排序區(qū)間中元素為空，算法結束。

class Sort{
public:
	void Insert_Sort(vector<int> &arr){
		//1.判斷溢出條件
		if(arr.size() < 2) return;
		int length =arr.size();
		int j =0;//初始的已排序區(qū)間的下標 
		for(int i =1;i < length ;i++){ //從未排序的區(qū)間里面取元素
			int temp =arr[i];
			j =i-1;    //不斷更新已排序區(qū)間
			while(j >= 0 && temp <a[j]){
				//如果小的話就往后移動，找到合適的插入位置 
				arr[j+1]=arr[j];
				j--; 
			} 
			arr[j+1]=temp;  //插入元素 
		} 
	}
};

選擇排序

選擇排序算法的實現思路有點類似插入排序，也分已排序區(qū)間和未排序區(qū)間。但是選擇排序每次會從未排序區(qū)間中找到最小的元素，將其放到已排序區(qū)間的末尾

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; 
		}
	}
};

歸并排序

歸并排序是由下而上，采用分治的思想，把數據先拆分在合并，并把合并后的數據存入臨時數組中，保證原先的數據位置不發(fā)生變化，是一種穩(wěn)定的排序但不是原地排序，時間復雜度是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];
		}
	}
};

快速排序

快速排序是先分區(qū)，在處理子問題，通過找到區(qū)間后取得任意一個分區(qū)點，小的放分區(qū)點左邊，大的放分區(qū)點右邊，時間復雜度是O(nlong),空間復雜度是O(1),是原地排序但不是穩(wěn)定排序

快排優(yōu)化的話，有：三數取中法，和隨機法，都是為了防止要排序的數組中有重復元素，這塊我演示的是隨機法

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語言排序的資料請關注腳本之家其它相關文章！

您可能感興趣的文章: