面试常见的排序算法

一、各个排序算法的时间复杂度

#include<iostream>
#include<vector>
using namespace std;

void Merg(vector<int>& vec, int L, int mid, int R) {
	vector<int>temp(R-L+1);
	int i = L, j = mid + 1;
	int index = 0;
	while (i <= mid && j <= R) {
		if (vec[i] < vec[j]) {
			temp[index++] = vec[i++];
		}
		else {
			temp[index++] = vec[j++];
		}		
	}
	 while (i <= mid) {
		temp[index++] = vec[i++];
		}	
	while (j <= R) {
		temp[index++] = vec[j++];
		}
	//把排好序的放回原数组
		index = L;
		for (auto it:temp) {
			vec[index++] = it;
		}
}
void Merg_sort(vector<int>& vec, int L, int R) {
	if (L >= R) return;
	int mid = (R - L) / 2 + L;
	Merg_sort(vec, L, mid);
	Merg_sort(vec, mid + 1, R);
	//合并
	Merg(vec, L, mid, R);
}
int main() {
	int num;
	vector<int>vec;
	 while (cin >> num) {
        vec.push_back(num);
    }
	Merg_sort(vec,0,vec.size()-1);
	for (auto it : vec) {
		cout << it << " ";
	}
	return 0;
}

二、堆排序

#include<iostream>
#include<vector>
using namespace std;

//将子树调整为最大堆
void Adjust(vector<int>& vec, int start, int end) {  //start最开始调整时start不断变化，交换时end不断缩小
	int father = start;    //当前子树结点
	int child = father * 2 + 1;   //左子树
	while (child <= end) { //不断向下调整防止破坏子树，用end来结束循环防止循环内数组访问越界（调整子树的子树的时候）
		if (child + 1 <= end && vec[child] < vec[child + 1]) {  //child+1判断右子树是否越界
			child++;
		}
		if (vec[father] < vec[child]) {
			swap(vec[father], vec[child]);
	//帮助调整子树的最大堆结构，只有和子树的根节点交换了才可能需要向下调整子树
		father = child;
		child = father * 2 + 1;
		}
		else {
			break;  //如果没交换child就会改变 会死循环
		}
	}
}
//堆排序的整个流程
void Heap_sort(vector<int>& vec)
{
	int n = vec.size(); //完全二叉树中结点个数

	//最后一个有子节点的下标为n/2-1;
	for (int i = n / 2 - 1; i >= 0; i--) {
		Adjust(vec, i, n - 1);  //end不受限制因为可能破坏子树结构向下调整
	}

	for (int i = n - 1; i >= 0; i--)  //i是下标
	{
		//交换堆顶和待排序元素中的最后一个元素
		swap(vec[0], vec[i]);

	//把剩下的待排序元素调整成最大堆结构
	Adjust(vec, 0, i - 1); //为啥到i-1，因为Adjust的区间是左闭右闭
	}
}
int  main() {
	vector<int>vec;
	int n;
	while(cin>>n){
		vec.push_back(n);
	}
	Heap_sort(vec);
	for (auto it:vec) {
		cout << it << " ";
	}

	return 0;
   }

三、快速排序

?

#include <iostream>
#include<vector>
#include <algorithm>
using namespace std;
int part(vector<int>& nums, int l, int r)  //划分函数
{
	int m=l+rand()%(r-l+1);
    swap(nums[m],nums[l]);
	int i = l, j = r, pivot = nums[l]; //基准元素
	while (i < j)
	{
		while (i<j && nums[j]>pivot) //从右向左开始找一个 小于等于 pivot的数值
		{
			j--;
		}
		if (i < j)
		{
			swap(nums[i++],nums[j]);  //r[i]和r[j]交换后 i 向右移动一位
		}
		while (i < j && nums[i] <= pivot) //从左向右开始找一个 大于 pivot的数值
		{
			i++;
		}
		if (i < j)
		{
			swap(nums[i], nums[j--]);  //r[i]和r[j]交换后 i 向左移动一位
		}
	}
	return i;  //返回最终划分完成后基准元素所在的位置
}
void Quicksort(vector<int>& nums, int l, int r)
{
	int mid;
	if (l < r)
	{
		mid = part(nums, l, r);  // 返回基准元素位置
		Quicksort(nums, l, mid - 1); // 左区间递归快速排序
		Quicksort(nums, mid+1, r); // 右区间递归快速排序
	}
}
int main()
{
	vector<int> vec;
	int n;
	while(cin>>n){
		vec.push_back(n);
	}
	Quicksort(vec, 0, vec.size()-1);
	for (auto it:vec) {
	cout << it << " ";
	}

	return 0;
}

#include<stdio.h>
#include<iostream>
using namespace std;

void swap(int* a, int* b) {
	int c = *a;
	*a = *b;
	*b = c;
}
void BubbleSort(int arr[],int n) {
	for (int i = 1; i < n; i++) {   
	int flat=0;
		for (int j = 0; j < n - i; j++) {
			if (arr[j] > arr[j + 1]) {
				swap(&arr[j], &arr[j + 1]);
				flat=1;
			}
		}
		if(flat==0){
		return;
		}
	}
}
int main() {
int n;
cin >> n;
int arr[n];
for (int i = 0; i < n; i++) {
    cin >> arr[i];
}
BubbleSort(arr, n);
for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
}

	return 0;
}

?

?

?

?

?

?