排序算法（一）

一、基本概念：

1.排序算法是一种很重要的算法，许多其他算法是以排序算法为基础的。排序算法主要有冒泡排序、插入排序、希尔排序、选择排序、堆排序、归并排序、快速排序。

2.内部排序：在内存空间里完成数据的排序，一次完成

3.排序的稳定性：如果两个大小相等的元素在排序后相对位置不变，则排序是稳定的

4.没有一种排序在任意情况下都是最好的，需要分情况使用

二、算法实现：

1.冒泡排序：大泡泡不断往上

（1）优化：设置一个tag，如果某一次排列都没有执行，则退出循环

（2）适用于链表

（3）只交换严格满足大于的元素，算法稳定

（4）时间复杂度：O(N2)

（5）算法实现（C++）：

void Bubble_sort(int a[], int n)
{
	for (int i =n-1; i !=0; i--)
	{
		for (int j = 0; j != i; j++)    //把最大的元素放到最后
		{
			if (a[j + 1] < a[j])    //只有严格小于才交换元素，算法是稳定的
			{
				int t = a[j];
				a[j] = a[j + 1];
				a[j + 1] = t;
			}
		}
	}
}

（6）算法优化：

void BBubble_sort(int a[], int n)
{
	int flag = 0;    //设置一个flag用于表示是否发生了交换
	for (int i = n - 1; i != 0; i--)
	{
		flag = 0;
		for (int j = 0; j != i; j++)    //一次冒泡
		{
			if (a[j + 1] < a[j])    
			{
				flag = 1;    //标识发生了交换
				int t = a[j];
				a[j] = a[j + 1];
				a[j + 1] = t;
			}
		}
		if (flag == 0)    //如果有任何一次没有发生交换，则退出循环
			break;
	}
}

2.插入排序：类似于打扑克牌抓牌

（1）每次抓一张牌，与前一张牌比较，比前一张小的话则把前一张牌向后移动，否则插入

（2）在序列基本有序的情况下，插入排序简单高效

（3）时间复杂度：O(N2)

（4）算法实现（C++）：

void Insertion_sort(int a[], int n)
{
	int i = 0;
	for (int p = 1; p != n; p++)
	{
		int temp = a[p];    //摸下一张牌
		for (i = p; i >= 1 && a[i-1] > temp; --i)
			a[i] = a[i - 1];    //移出空位
		a[i] = temp;    //插入新牌
	}
}

3.希尔排序：对插入排序的优化，预先使序列有序一点

（1）设置一个增量序列，对每个增量序列进行插入排序

（2）时间复杂度：选取不同的增量序列时间复杂度不同，通常为O(N1.5)

（3）算法实现（增量序列N/2）：

void Shell_sort(int a[], int n)
{
	for (int D = n / 2; D != 0; D /= 2)    //增量序列
	{
		int i = 0, p = 0;
		for (p = D; p != n; p++)    //一次增量排序
		{
			int temp = a[p];
			for (i = p; i >= D && a[i - D] > temp; i -= D)    
				a[i] = a[i - D];
			a[i] = temp;
		}
	}
}

4.选择排序：每次从无序序列中选择最小的元素放入有序序列的末尾

（1）时间复杂度：O(N2)

（2）每执行一次，都把最小元素放到序列最前面

（3）算法实现：

void Selection_sort(int a[], int n)
{
	for (int i = 0; i != n-1; i++)    //n次排序，每次把最小的元素与最左边元素交换
	{
		int min = i;
		for (int j = i+1; j != n; j++)    //查找未排序部分的最小元素的下标
			if (a[j] < a[min])
				min = j;
		int t = a[i];    //交换元素
		a[i] = a[min];
		a[min] = t;
	}
}

三、举个栗子（leetcode973.最接近原点的k个点）

（1）首先采用插入排序算法，但是运行超过了时间限制

（2）考虑使用选择排序，只需进行K次即可

vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
        Selection_sort(points,K);
	    vector<vector<int>> out;
	    for (int i = 0; i != K; i++)
		    out.push_back(points[i]);
	    return out;
    }
    void Selection_sort(vector<vector<int>>& v,int K)
    {
	    int min = 0;
	    int min_t = 0;
	    int p = 0;
	    for (int i = 0; i !=K; i++)
	    {
		    min = v[i][0] * v[i][0] +v[i][1] * v[i][1];
		    min_t = i ;
		    for (p = i+1 ; p != v.size(); p++)
		    {
			    int temp = v[p][0] * v[p][0] + v[p][1] * v[p][1];
			    if (temp < min)
			    {
				    min_t = p;
				    min = temp;
			    }
				
		    }
		    if (min_t != i)
		    {
			    vector<int> temp2 = v[i];
			    v[i] = v[min_t];
			    v[min_t] = temp2;
		    }
	    }

（3）可以用堆排序进行优化