[数据结构与算法] 十大排序算法

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 十大排序算法 -> 正文阅读

[数据结构与算法]十大排序算法

稳定性：指该算法是否会改变序列中相同元素的相对位置。（不稳定口诀：快[快排]些[希尔]选[选择]一堆[堆排]）
就地性（内部排序）：该算法最多额外创建几个辅助变量，不再申请过多的辅助空间。亦即，就地排序算法不会新创建一个有序序列，空间复杂度为 O(1)。

算法	稳定性	就地性	时间复杂度	空间复杂度
冒泡排序	稳定	?	O(n2)	O(1)
插入排序	稳定	?	O(n2)	O(1)
希尔排序	不稳定	?	O(n^1.5)	O(1)
选择排序	不稳定	?	O(n2)	O(1)
归并排序	稳定	×	O(N*logN)	O(N)
快速排序	不稳定	?	O(N*logN)	O(logN)
堆排序	不稳定	×	O(N*logN)	O(1)
基数排序	稳定	×	O(n*k)	O(n+k)
桶排序	稳定	×	O(n+k)	O(n+k)
计数排序	稳定	×	O(n+k)	O(k)

冒泡排序

不稳定 | 就地 | O(n2) | O(1)
相邻两数比较，较大数下沉，较小数冒起

void BubbleSort(int arr[], int size)
{
	for (int i = 0; i < size-1; i++)
	{
		for (int j = 0; j < size-i-1; j++)
		{
			if (arr[j]>arr[j + 1])
			{
				int temp;
				temp = arr[j];
				arr[j] = arr[j+1];
				arr[j + 1] = temp;
			}
		}
	}
}

插入排序

稳定 | 就地 | O(n2) | O(1)
假设前N-1个数已经排好序，将第N个数插入到该有序数列中，反复操作直到排序完成。

//直接插入
void InsertSort(int arr[], int size)
{
	//第1个数已经有序，从arr[1]开始
	for (int i = 1; i < size; i++)
	{
		int tmp = arr[i];
		for (int j = i - 1; j >= 0; j--)
		{
			if (tmp < arr[j])//如果第二个数比第一个数大的话，就要交换
				arr[j + 1] = arr[j];
			else break;
			
		}
		arr[j + 1] = tmp;
	}
}

//折半插入（二分法）
void BinInsertSort(int arr[], int size)
{
	for (int i = 1; i < size; i++)
	{
		int tmp = arr[i];
		//二分查找插入位置
		int left = 0, right = i-1;
		while (left <= right) {
			int mid = left + (right - left)/2;
			if ( tmp < arr[mid] ) right= mid-1;
			else left = mid + 1;
		}
		//插入
		for (j = i - 1; j >= left; j--)
				arr[j + 1] = arr[j];
		arr[left] = tmp;
	}
}

希尔排序

不稳定 | 就地 | O(n^1.5) | O(1)
选择某一增量（数组大小/2），将待排数列分为若干子序列（例如arr[8]选择增量为4，则arr[0]和arr[4]为一组，两两一组共4组），分别对每个子序列进行插入排序。逐渐减小增量，重复操作，直到增量为1，进行最后的插入排序，排序完成。

void ShellSort(int arr[], int size)
{
	//每轮增量除以2
	for (int gap = size / 2; gap > 0; gap /= 2)
	{
		//同组元素进行插入排序
		for (int i = gap; i < size; i++)
		{
			int tmp = arr[i];
			for (int j = i - gap; j>=0; j-=gap)
			{
				if (tmp < arr[j])
					arr[j + gap] = arr[j];
				else break;
			}
			arr[j + gap] = tmp;
		}
	}
}

选择排序

不稳定 | 就地 | O(n2) | O(1)
第一次遍历N-1个数，找到最小值与第一个元素交换；第二次遍历N-2个数，找到最小值与第二个元素交换；直到第N-1次遍历，找到最小值与第N-1个元素交换，排序完成。
或者每次把最大数当道最后一个位置，直到还剩下一个数。

//法一
void SelectSort(int arr[], int size)
{
	for (int i = 0; i < size - 1; i++)
	{
		int minIdx = i;
		//找到最小值的索引
		for (int j = i+1; j < size; j++)
		{
			if (arr[j]<arr[minIdx])
				minIdx = j;
		}
		//找到后将最小值放到第一个位置
		int tmp = arr[i];
		arr[i] = arr[minIdx];
		arr[minIdx] = tmp;
	}
}
//法二
void SelectSort(int arr[], int size)
{
	for (int i = size; i > 1; i--)
	{
		int maxIdx = 0;
		//找到最大值的索引
		for (int j = 0; j < i; j++)
		{
			if (arr[j]>arr[maxIdx])
				maxIdx = j;
		}
		//找到后将最大值放到最后一个位置
		int tmp = arr[i - 1];
		arr[i - 1] = arr[maxIdx];
		arr[maxIdx] = tmp;
	}
}

归并排序

稳定 | 非就地 | O(N*logN) | O(N)
将初始序列的N个元素看成N个子序列，两两归并为有序的序列,此时序列的长度为2，再两两归并为有序的序列，此时序列的长度为4，…，直至得到一个长为N的序列，排序完成。


void MergeSort(int arr[], int begin, int end)
{
	//拆分子序列
	if(begin>= end) return; //直到每个子序列长度为1
	int mid = (begin+ end) / 2;
	MergeSort(arr, begin, mid);
	MergeSort(arr, mid + 1, end);
	//再将两个子序列合并成一个有序序列
	MergeArr(arr, begin, mid, end); 
}

//合并子序列
void MergeArr(int arr[], int begin, int mid, int end)
{
	int *tmpArr = new int[end - begin + 1];
	int i = begin, j = mid + 1, k = 0;
	//比较大小，合并到tmpArr中
	while (i <= mid && j <= end) {
		if ( arr[i] < arr[j] ) {
			tmpArr[k] = arr[i];
			i++;
		}
		else {
			tmpArr[k] = arr[j];
			j++;
		}
		k++;
	}
	//没有比较完的元素直接复制到tmpArr
	while (i <= mid) {
		tmpArr[k] = arr[i];
		i++;
		k++;
	}
	while (j <= end) {
		tmpArr[k] = arr[j];
		j++;
		k++;
	}
	//合并完成，返回结果
	i = begin;
	for (int tmp = 0; tmp < k && i <= end; tmp++) {
		arr[i] = tmpArr[tmp];
		i++;
	}
	delete[] tmpArr;
	tmpArr = NULL;
}

快速排序

不稳定 | 就地 | O(N*logN) | O(logN)
从待排数列中取出一个数作为key（通常选第一个数）；将比key小的数全部放在其左边，大于或等于的数全部放在其右边；对左右两个小数列重复上述操作，直到各区间只有1个数，排序完成。

//法一：递归实现
void QuickSort(int arr[],int left, int right)
{
	if (left >= right) return;
	int begin = left, end = right;
	int key = arr[left]; //选取最左边元素为key
	while (begin < end)
	{
		/* 由于key选的最左边的元素，所以每次必须是end先移动 */
		//指针end从后向前找比key小的元素
		while (arr[end] >= key && begin<end) end--;
		//指针begin从前向后找比key大的元素
		while (arr[begin] <= key && begin<end) begin++;
		//若begin和end没有相遇，则交换begin和end所指的元素
		if (begin < end)
		{
	    	int tmp = arr[begin];
			arr[begin] = arr[end];
			arr[end] = tmp;
		}
		//交换后重复操作，直到begin和end相遇，指向同一元素
	}
	//key归位，此时key左边的元素都比它小，右边的都比它大
	arr[left] = arr[begin];
	arr[begin] = key;
	
	//递归，再分别对左右两边的元素排序
	QuickSort(arr,left, begin - 1);
	QuickSort(arr, begin + 1, right);
}

//法二：栈实现
int findKey(int arr[],int left, int right) 
{
	int key = arr[left]; //选取最左边元素为key
	int begin = left, end = right;
	while (begin < end)
	{
		/* 由于key选的最左边的元素，所以每次必须是end先移动 */
		//指针end从后向前找比key小的元素
		while (arr[end] >= key && begin<end) end--;
		//指针begin从前向后找比key大的元素
		while (arr[begin] <= key && begin<end) begin++;
		//若begin和end没有相遇，则交换begin和end所指的元素
		if (begin < end)
		{
	    	int tmp = arr[begin];
			arr[begin] = arr[end];
			arr[end] = tmp;
		}
		//交换后重复操作，直到begin和end相遇，指向同一元素
	}
	//key归位，此时key左边的元素都比它小，右边的都比它大
	arr[left] = arr[begin];
	arr[begin] = key;
	
	return begin;
}
void QuickSort(int arr[],int left, int right)
{
	stack<int> st;
	if (left < right) {
		int mid = findKey(arr, left, right);
		//将起点终点压栈
		if (mid - 1 > left) {
			st.push(left);
			st.push(mid - 1);
		}
		if (mid + 1 < right) {
			st.push(mid + 1);
			st.push(right);
		}
		//从栈中取出序列索引
		while (!st.empty()) {
			int r = st.top();
			st.pop();
			int l = st.top();
			st.pop();
			mid = findKey(arr, l, r);
			//将新序列入栈
			if (mid - 1 > l) {
				st.push(l);
				st.push(mid - 1);
			}
			if (mid + 1 < r) {
				st.push(mid + 1);
				st.push(r);
			}
		}
	}
}

堆排序

不稳定 | 非就地 | O(N*logN) | O(1)

把待排序的元素放在堆中，每个结点表示一个元素；
找到树的最后一个非叶节点，建立初堆；
将根结点与堆的最后一个结点交换，之后重建堆的对象为n-1个，再把次大的结点与倒数第二个结点交换，之后重建堆的对象为n-2个，…，以此类推，直至重建堆的对象为0，排序完成。

void display (int arr[], int size)
{
	for (int i = 0; i < size; i++)
		cout << arr[i] << " ";
	cout << endl;
}

// 堆排序（大堆：升序）
void AdjustDwon(int arr[], int size, int root) {
	int parent = root;
	int child = parent*2+1; //左孩子下标
	while (child<size) {
		//取左右孩子中更大的那个节点值
		if (child + 1 < size && arr[child + 1] > arr[child])
			child ++;
		//若孩子节点值更大，则交换父子节点
		if (arr[child] > arr[parent]) {
			int temp = arr[parent];
			arr[parent] = arr[child];
			arr[child] = temp;
 
			parent=child;
			child = parent * 2 + 1;
		}
		else  break;
	}
}
 
void HeapSort(int arr[], int size) {
	if (size == 0) return;
	
	//找到树的最后一个非叶节点，初始化堆
	//即从倒数第二排开始，遍历每个非叶节点，使其符合大堆规则
	for (int i = (size - 2) / 2; i >= 0; i--) 
		AdjustDwon(arr, size, i);
	display (arr, size);
	
	for (int i = size - 1; i >= 0; --i) {
		//交换顶点和末尾元素
		int temp = arr[i];
		arr[i] = arr[0];
		arr[0] = temp;
		//重新建立大顶堆
		AdjustDwon(arr, i, 0);
	}
	display (arr, size);
}

基数排序

稳定 | 非就地 | O(n*k) | O(n+k)

对于一组数，先按照个位排序，再按照十位排序，再按照百位排序，…，直到排序完成。

//求该组数据中的最高位是什么位
int maxbit(int data[], int n) 
{
    int d = 1; //保存最大的位数
    int p = 10;
    for(int i = 0; i < n; ++i)
    {
        while(data[i] >= p)
        {
            p *= 10;
            ++d;
        }
    }
    return d;
}
void radixsort(int data[], int n)
{
    int d = maxbit(data, n);
    int tmp[n];
    int radix = 1;
    for(int i = 1; i <= d; i++) //共进行d次排序
    {
        int count[10] = {0}; //每轮新建一个计数器
        for(int j = 0; j < n; j++)
        {
            int idx = (data[j] / radix) % 10; //统计每个桶中的记录数
            count[idx]++;
        }
        for(int j = 1; j < 10; j++)
            count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶
        for(int j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中
        {
            int idx = (data[j] / radix) % 10;
            tmp[count[idx] - 1] = data[j];
            count[idx]--;
        }
        for(int j = 0; j < n; j++) //将临时数组的内容复制到data中
            data[j] = tmp[j];
        radix = radix * 10;
    }
}

桶排序

稳定 | 非就地 | O(n+k) | O(n+k)

设置有限数量的空桶，并将数据依次放入对应的空桶中；
对每个不为空的桶再各自进行排序（可能使用别的排序算法，或以递归方式继续使用桶排序）；
最后将每个非空桶中排好的元素放回到原数组中。

void insert(list<int>& bucket,int val)
{
    auto iter = bucket.begin();
    while(iter != bucket.end() && val >= *iter) ++iter;
    //insert会在iter之前插入数据，这样可以稳定排序
    bucket.insert(iter,val);
}

void BucketSort_1(vector<int>& arr)
{
    int len = arr.size();
    if(len <= 1)
        return;
    int min = arr[0],max = min;
    for(int i=1;i<len;++i)
    {
        if(min>arr[i]) min = arr[i];
        if(max<arr[i]) max = arr[i];
    }
    int k = 10;//k为数字之间的间隔
    //向上取整，例如[0,9]有10个数，(9 - 0)/k + 1 = 1;
    int bucketsNum = (max - min)/k + 1;
    vector<list<int>> buckets(bucketsNum);
    for(int i=0;i<len;++i)
    {
        int value = arr[i];
        //(value-min)/k就是在哪个桶里面
        insert(buckets[(value-min)/k],value);
    }
    int index = 0;
    for(int i=0;i<bucketsNum;++i)
    {
        if(buckets[i].size())
        {
            for(auto& value:buckets[i])
                arr[index++] = value;
        }
    }
}

计数排序

稳定 | 非就地 | O(n+k) | O(k)

找到待排序数组的最大值max和最小值min；
统计数组中每个数字出现的次数，存入辅助数组中；
对辅助数组总数累计（后面的值出现的位置为前面所有值出现的次数之和）；
逆序输出辅助数组中的值。

void countSort(vector<int>& arr)
{
    int len = arr.size();
    if(len == 0) return;
    
    vector<int> tempArr(arr.begin(),arr.end()); //需要一个原始数组的拷贝
    //查找min，max
    int min = tempArr[0],max = min;
    for(int i=1;i<len;++i)
    {
        if(min>tempArr[i])
            min = tempArr[i];
        if(max<tempArr[i])
            max = tempArr[i];
    }

    //统计每个数字的出现次数
    const int k = max-min+1;
    int count[k]={0};
    for(int i=0;i<len;++i)
        ++count[tempArr[i]-min]; //注意偏移量min
    for(int i=1;i<k;++i)
        count[i] +=count[i-1]; //后面的键值出现的位置为前面所有键值出现的次数之和，也就是每个数所在的范围

	//这里是逆序排序，这个和我们统计每个数字出现的位置有关系，
	//比如0出现了3次，加上之前-1出现的次数，就是4。
	//我们倒序排序第一个key值为0的时候，那么在count中的大小应该是4，那么它在arr数组的下标就该是4-1，count自减1为3
	//排序第二个key值为0的时候，count为3，在arr数组的下标是3-1
    for(int i=len-1;i>=0;--i)
        arr[--count[tempArr[i] - min]] = tempArr[i]; 
        //这里--count[tempArr[i] - min]很精简
        //又解决了下标需要减1的问题，对应的count数组中的值也减1
}