算法——常用排序算法（上）（C++实现）

阳光穿透心脏的1/2处 2021-12-10 12:13 336阅读 0赞

# 冒泡排序（bubblesort） #

## 思路 ##

无论从大到小还是从小到大，都是先排最尾部的数然后依次往前。时间复杂度为 O ( N 2 ) O(N^\{2\}) O(N2)

## 代码 ##

#include<iostream>
    using namespace std;
    //冒泡实现从大到小
    int bubblesort(int arr[],int n)
    {
    	//两次循环：i遍历n次，j遍历n次，故时间复杂度为O(N*N)
    	for (int i = 0; i <n - 1; i++)
    	{
    		for (int j = 0; j < n - 1 - i; j++)
    		{
    			//相邻位置前一个比后一个小则交换
    			if (arr[j] < arr[j + 1])
    			{
    				int temp = arr[j + 1];
    				arr[j + 1] = arr[j];
    				arr[j] = temp;
    			}
    		}
    		//打印每一次冒泡结果
    		for (int i = 0; i < n; i++)
    		{
    			cout << arr[i] << "";
    		}
    		cout << endl;
    	}
    	return 0;
    }
    //测试用例
    int main()
    {
    	int arr[7] = { 6,3,2,4,1,5,7 };
    	bubblesort(arr,7);
    	return 0;
    }

# 选择排序 #

## 思路 ##

时间复杂度为 O ( N 2 ) O(N^\{2\}) O(N2)

## 代码 ##

#include<iostream>
    using namespace std;
    /*选择排序实现从小到大,时间复杂度为O(N*N)*/
    int selectsort(int arr[], int n)
    {
    	for (int i = 0; i < n ; i++)
    	{
    		int tempmin = i;
    		for (int j = i; j < n  ; j++)
    		{
    			//找出j开始的最小数放在arr[tempmin]
    			if (arr[j] < arr[tempmin])
    				tempmin = j;	
    		}
    		//将找到的tempmin放置在i位置上
    		if (arr[i] > arr[tempmin])
    		{
    			int temp = arr[i];
    			arr[i] = arr[tempmin];
    			arr[tempmin] = temp;
    		}
    	}
    	//输出排好的数组
    	for (int i = 0; i < n; i++)
    	{
    		cout << arr[i] << "";
    	}
    	cout << endl;
    	cout << "-------------------" << endl;
    	return 0;
    }
    //测试用例
    int main()
    {
    	int arr[6] = { 2,6,3,5,1,7 };
    	selectsort(arr, 6);
    	return 0;
    }

# 插入排序 #

## 思路 ##

时间复杂度总体为 O ( N 2 ) O(N^\{2\}) O(N2)。插入排序的时间复杂度与数据状况有关，最好情况是 O ( N ) O(N) O(N)最差情况为 O ( N 2 ) O(N^\{2\}) O(N2)，考虑算法性能时一律按照最差算。

## 代码 ##

#include<iostream>
    using namespace std;
    int insertsort(int arr[], int len)
    {
    	for (int i = 0; i < len-1; i++)//i为有序数组的最后一个元素
    	{
    		int temp = arr[i + 1];//temp为待插入元素，初值为arr[i + 1]
    		int j = i;
    		//寻找插入位置
    		while (j >= 0 && temp < arr[j])
    		{
    			arr[j + 1] = arr[j];//大于temp的元素往后移动
    			j--;
    		}
    		arr[j + 1] = temp;//temp后移
    		for (int i = 0; i < len; i++)
    		{
    			cout << arr[i] << "";
    		}
    		cout << endl;
    	}
    	cout << "-------------------" << endl;
    	//输出排好的数组
    	for (int i = 0; i < len; i++)
    	{
    		cout << arr[i] << "";
    	}
    	cout << endl;
    	return 0;
    }
    //测试用例
    int main()
    {
    	int arr[6] = { 2,6,3,5,1,7 };
    	insertsort(arr, 6);
    	return 0;
    }

# 总结 #

以上三种排序时间复杂度均为 O ( N 2 ) O(N^\{2\}) O(N2)，冒泡排序和插入排序都具有稳定性，选择排序不稳定。工程上，冒泡和选择排序应用较少。