【排序】八种常用排序

【排序】八种常用排序,第1张

1.插入排序

2.希尔排序

3.选择排序

4.堆排序

5.冒泡排序

6.快速排序

7.归并排序

8.计数排序

---------------

插入排序

这个排序原来很简单,如图演示:

我们先把 9 看作有序数组插入,它比8大,那就交换位置

 

此时,8前面没有数字了,所以它就停下,再把8 9 看作有序数组:

再把 7 插入,因为9比7大,交换,8比7大,交换,就是这样:

重复这样的步骤,直到数组结/或者已经交换完全

实现代码如下:

// 插入排序
void InsertSort(int* a, int n)
{
    //因为tmp是当前下标的后一个元素比较,所以最后一个元素的位置是n-1
	for (int i = 0; i < n-1; i++)
	{
		int n = i;
		int tmp = a[1 + n];
        //假设每次都要比到最后
		while (n >= 0)
		{
            //如果小于,就让这个位置元素被替代,然后再跟前一个比较
			if (tmp < a[n])
			{
				a[n + 1] = a[n];
				n -= 1;
			}
            //如果不小,那就退出
			else
			{
				break;
			}
		}
        //它停下的位置就是前面已经没有比它小的元素了,但是因为上面替换之前-1,所以这里要+1
		a[n + 1] = tmp;
	}
}

-----------

时间复杂度:最好O(N^2),最坏O(N^2),因为它总要比较判断

空间复杂度:O(1),没有额外开辟空间

时间太慢了,不是很推荐

---------------

希尔排序

插入排序属实太慢了,假设一个很小的元素在最后面,那它要移动N次才能来到前面的位置(1在最后面,它要来到9的位置就要换8次)

所以它的改进版本,希尔排序就出来了,希尔排序是这么想的,有一个间隔数gap,这个数可以很大,也可以很小,它先将数组分为几个小组:

红色一组为:9 6 3

蓝色一组为:8 5 2

绿色一组为:7 4 1

我这里设置的gap是3,应该可以看的出来,然后分别对这几个小组排序:

9 6 3 变成 3 6 9 

8 5 2 变成 2 5 8 

7 4 1 变成 1 4 7 

就变成这样,这里只是举例子,因为降序方便看就设置为这样,实际要混乱一点,然后再对这降序的再排一次(这里已经有序了就没画)

每一次排序都会让数组更加有序

如果这个gap很大,那小的数组会更快的来到前面,因为它一次可以跳gap格,大的也会更快的去到后面

如过这个gap很小,那它每次移动都会给更加有序,如果是1,那就跟插入排序一样了

这个gap肯定不能太小,并且不能是固定的数字,如果是固定的数字,那它每次移动就会很慢,所以最好跟N扯上关系,如果看懂了插入排序,那希尔就很好理解,它不过是把 n+1 变成了 n+gap,然后再插入

// 希尔排序
void ShellSort(int* a, int n)
{
    //定义一个gap
	int gap = n;
	while (gap > 1)
	{
        //这个值就是间隔
		gap = gap / 3 + 1;
        //每次都是跟 n+gap比较,所以最后一个比较元素的位置是n-gap
		for (int i = 0; i < n - gap; i++)
		{
            //从这个下标开始,如果直接拿i的话会死循环
			int n = i;
			int tmp = a[n + gap];
            //如果这个n>0,那它前面还有没比较的值
			while (n >= 0)
			{
                //比较
				if (tmp < a[n])
				{
                    //交换,并且让n-gap,找到下一个间隔为gap的比较
					a[n + gap] = a[n];
					n -= gap;
				}
				else
				{
					break;
				}
			}
            //同理,最后一次这个n肯定被-gap,所以加上
			a[n+gap] = tmp;
		}
	}
}

时间复杂度: O (n *logn)

空间复杂度:O(1)

 这个算法非常快,建议使用

-----------------

选择排序

最好理解的排序,每次找最大的(或者最小的),也可以一起找出来,然后跟第一个元素和最后一个元素换位置,换完就排完了

然后交换,找出次大的,次小的:

循环即可 ,但是一定要注意,因为这里一次交换两个值,所以可能出现:

原本最大值的下标是0,然后最小值的下标是3,最小值先跟0的位置换,这个最大值就被交换到3的位置去了,再去交换下标0就会找到最小值,所以先判断交换位置有没有冲突,有就调整

// 选择排序
void SelectSort(int* a, int n)
{
    //要交换的左右下标
	int left = 0, right = n - 1;
	while (left < right)
	{
        //找出数组里面最大值和最小值的下标
		int max, min;
		max = min = left;
		for (int i = left+1; i <= right; i++)
		{
			if (a[i] > a[max])
			{
				max = i;
			}
			if (a[i] < a[min])
			{
				min = i;
			}
		}
        //交换
		swap(&a[left], &a[min]);
        //如果最大值的下标是上面的left,那它就会被交换到min的位置,所以让max指向被交换后的位置
		if (max == left)
		{
			max = min;
		}
        //再次交换
		swap(&a[right], &a[max]);
        //再换下一组
		left++;
		right--;
	}
}

时间复杂度:最好O(N^2),最坏O(N^2),因为不管怎么样它都要查找然后交换

空间复杂度:O(1),没有额外开辟空间

不是很快,不推荐使用

-----------

堆排序

这个在我以前专栏里面有详细说过,如果不了解堆的性质可以去看看,这里简单描述一下:

一个堆的堆顶是数组里面的最大值,那它就是大堆

一个堆的堆顶是数组里面的最小值,那它就是小堆

假设我们是升序,那我们就要建立大堆(降序建小堆),然后把堆顶的元素(也就是下标为0的元素)跟最后一个元素换,然后再调整一下堆即可

这里我就直接上代码实现了:

先是建立大堆的调整函数:

void AdjustDown(int* arr, int* root, int* end)
{
    //父亲节点
	int parent = root;
    //孩子节点
	int child = parent * 2+1;
	while (child < end)
	{
        //选两个孩子里面大的那个
		if (arr[child + 1] > arr[child] && (child+1) 

然后是排序:

// 堆排序
void HeapSort(int* a, int n)
{
        //先建立一个大堆
		for (int i = (n - 2)/2; i >= 0; --i)
		{
			AdjustDown(a, i, n);
		}
        //最后一个元素的下标,交换使用
		int end = n - 1;
		while (end)
		{
            //将最大的放到最后
			swap(&a[end], &a[0]);
			end--;
            //重新调整堆
			AdjustDown(a, 0, end);
		}
}

时间复杂度: O (n *logn)

空间复杂度:O(1)

 这个算法跟希尔排序一个级别,除了代码比较多以外,还是很推荐的

-------------

冒泡排序

老朋友了,我相信这个我不说大家也明白,具体思路是:

如果前面一个大于后面一个,交换,然后遍历数组

// 冒泡排序
void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (a[j - 1] > a[j])
			{
				swap(&a[j - 1], &a[j]);
			}
		}
	}
}

就不写注释了,实在太简单了

时间复杂度:O(N^2)

空间复杂度:O(N)

不推荐使用,太慢了,太慢了,太慢了!!!

如果代码没问题但时间超时,多半是它的锅,别用

-------------

快速排序

这个不是那个qsort,但也挺快的

有好几种思路,先说第一种:

1、hoare版:

使用递归,看图演示:

假设这是要排序的数组,第一步,我们选一个数字作为Key,这里我选 6(第一个元素的位置) ,那我们就从6开始走,先走Key的另一边,如果我选左边,那就先走右边,选右边就先走左边:

右边要找到比Key小的值,因为Key是6,这里2比6小,所以停下

然后找左边:

 左边找比Key大的值,5 4 都不符合条件,所以跳过,9比6大,所以停下,然后我们交换位置:

然后右边再继续先走,找到比6小的:,左边找比6大的

右边停在1,左边停在8,停下再次交换:

此时右边再开始走:

 

它们相遇了,这个时候我们就把这个位置的值跟Key(第一个元素的位置交换):

到这里,第一次就走完了,我们发现比Key小的都在左边,比Key大的都在右边,而6也来到了正确的位置,它的左边都比它小,它的右边都比它大

然后我们将数组分割:

在这两个数组里面重复上面的步骤,直到它们不可再分割为止:

第一次分割将数组分为两半,第二次将左边长的一段又变成两段...

看看代码理解:

// 单趟快排
int PartSort(int* a, int left, int right)
{
    //先将left现在的值保留下来(一般是0)
	int keyi = left;
    //如果左边大于右边那肯定相遇了
	while (left < right)
	{
		// 找小
		while (left < right && a[right] >= a[keyi])
			--right;

		// 找大
		while (left < right && a[left] <= a[keyi])
			++left;
        
        //交换
		swap(&a[left], &a[right]);
	}

    //出来了就是相遇,这里的元素跟Key交换
	swap(&a[keyi], &a[left]);

    //返回中间的节点,将其分割为两段
	return left;
}

 这是一趟,我们递归调用:

void QuickSort(int* a, int begin, int end)
{
	// 如果起始位址等于(或者大于)终点为止,那就可以返回了
	if (begin >= end)
		return;

    //这个值就是中点
	int keyi = PartSort(a, begin, end);
	
    //左半边,因为Key已经到了正确的为止,所以不用排了,left通常是0
	QuickSort(a, begin, keyi - 1);
       
    //右边,Key不排,结束为止就是end(数组长度)
	QuickSort(a, keyi + 1, end);
	return;
}
2、挖坑法

这种思路是这么的:

假设现在有这么一组数据,将最左边这个 6 保存下来,并让一个值指向这里,我们称之为pit(坑位)。

程序开始走,因为坑位在左边,所以要从右边开始走,right 从 7 开始,它的目标是找到比 6 小的数字:

7 < 6 ?

8 < 6 ?

9 < 6 ?

1 < 6 ?

它就停下来了 ,此时它指向 1 ,1 < 6 

找到了小,我们就让 1 放到坑位里面,坑位就是这里的 6 :

此时,因为坑位到了右边,下一次就要从左边开始走,left 从 5 开始,找比 6 大的:

5 < 6 ?

4 < 6 ? 

3 < 6 ?

2 <6 ?

1 < 6 ?

此时 left 来到 right 的位置,它们重叠了,而这里正好是 1 的位置,将一开始保存的 6 放到这里:

一趟排序就完成了,左边都是比 tmp(6) 小的,右边都是比它大的,随后我们递归调用即可:

// 快速排序挖坑法
int PartSort2(int* a, int left, int right)
{
    //坑位
	int pit = left;
    //key
	int key = a[left];
    //一趟走N次
	while (left < right)
	{

        //找小
		while (a[right] > key && left < right)
		{
			right--;
		}

        //将找到的小放到坑里面,然后将这里变成新的坑
		a[pit] = a[right];
		pit = right;

        //找大
		while (a[left] < key && left < right)
		{
			left++;
		}

       //将找到的大放到坑里面,然后将这里变成新的坑
		a[pit] = a[left];
		pit = left;
	}

    //它们相遇的位置,就是key的位置
	a[left] = key;
}

------------- 

3、前后指针法

 第一个指针指向 6 

第二个指针指向 5

key 是第一个元素 6

如果 cur 位置的元素大于 key 并且  ++prev 的位置不等于 cur ,那就交换:

 

5 < 6 ? cur++;

4 < 5 ?   ++prev == cur ?

交换它们的值:

 

cur++;

 3 < 6 ? ++prev == cur?

再次交换:

cur++; 

 .....

直到:

 此时,cur处元素大于key,所以不执行交换,但是cur++

cur 大于 key

cur++

 

cur 大于 key

cur++

此时cur越界,所以循环停下,将prev的值跟key的值交换:

 

第一趟结束

// 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{
    //前、后指针
	int prev = left;
	int cur = prev + 1;
    //key的值
	int key = left;
	while (cur <= right)
	{

        //开始走
		if (a[cur] < a[key] && a[++prev] != a[cur])
		{
			swap(&a[prev], &a[cur]);
		}

        //每次cur都++
		cur++;
	}
    
    //交换
	swap(&a[prev], &a[key]);

	return prev;
}

 ----------

如何优化快排

小区间优化:

但看快排的代码,它是靠递归完成的,这样的一个好处是可以把一个很麻烦的问题分成小问题解决

但是缺点同样很明显,假设这一次只要排 4 个数据,你还分成好几个小块,就有点太麻烦了,所以我们可以在快排里面调用一下 插入排序,当要排序的小于一定个数时,就不递归了,直接排序

void QuickSort(int* a, int begin, int end)
{
	// 如果起始位址等于(或者大于)终点为止,那就可以返回了
	if (begin >= end)
		return;

	//小于13个就插入,这个区间可以自己定
	if (end - begin + 1 < 13)
	{
		InsertSort(a, end - begin + 1);
		return;
	}

	//这个值就是中点
	int keyi = PartSort3(a, begin, end);

	//左半边,因为Key已经到了正确的为止,所以不用排了,left通常是0
	QuickSort(a, begin, keyi - 1);

	//右边,Key不排,结束为止就是end(数组长度)
	QuickSort(a, keyi + 1, end);
	return;
}

选择优化

另外,还有一个可以优化的地方,如果每次快排的 key 都是数组中间的数,那它的时间复杂度是

N*logN,那它的最坏情况呢?

如果每次都选到两边的数据,那它的时间复杂度毫无疑问的是 N^2,针对这种情况,我们还可以优化一个函数,确保key不是数组两边的数

int FindKey(int* a, int left,int right)
{

    
	int key = left + (left + right) / 2;
	if (a[left] < a[key])
	{
		if (a[right] > a[key])
		{
			return key;
		}
		else if (a[left] > a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else
	{
		if (a[key] > a[right])
		{
			return key;
		}
		else if (a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}

看着复杂,不过不算难,再将用到Key的地方全部换成这个函数优化key的选择,快排还能还进一步...


非递归实现

如何实现非递归?

那我们就要好好想想递归是来做什么的:

 这是要排序的数组,快排递归实现就是如下图所示:

它会将选定的key排到它应该有的位置,而 左边都比它小,右边都比它大,随后,它将key左边传入函数,再递归,再将右边传入函数递归:

每一次,它都至少可以保证一个数字来到应该有的位置上,如此反复

...

如果要非递归,那我们就要实现的是每一次都传入一个区间,直到每个区间都覆盖到,这里就要用到之前的 队列/栈

我这里用的是栈, 在用之前,要先把栈的函数拷贝一份:


void StackInit(Stack* ps)
{
	assert(ps);
	ps->arr = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : (ps->capacity) * 2;
		ps->arr = (STDataType*)realloc(ps->arr, sizeof(Stack)* newcapacity);
		if (ps->arr == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		ps->capacity = newcapacity;
	}
	ps->arr[ps->top++] = data;
}

void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->top > 0);
	ps->top--;
}

STDataType StackTop(Stack* ps)
{
	assert(ps);
	return ps->arr[ps->top-1];
}

int StackSize(Stack* ps)
{
	assert(ps);
	return ps->top;
}

int StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top == 0;
}

void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->arr);
	ps->arr = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

都是之前写过也用过好几次的代码了,这里就不重复说明了

思路是这样的:

已有一个数组,将它最左边的和最右边的下标压下去

这里压的是 6 和 8

循环判断,如果栈不为空,就进去

随后拿两个值来接收栈里面的值,一个是左下标,一个是右下标,对这一块空间排序

然后对它进行一次排序,随后它应该会被分成两块:

 

可以看到key左边是一块待排序的空间,右边也是一块待排序的空间

将它的左边压栈,它左边的空间是 0 - key-1

将它的右边压栈,它右边的空间是 key+1 - end(数组末尾)

不过在压栈之前,最好先判断一下它们中间有没有数据

如果此时数组还没排完,那栈里面应该还压着其他区间,随后再次读取数据

直到栈为空

void QuickSortNonR(int* a, int left, int right)
{
    //创建栈并初始化
	Stack st;
	StackInit(&st);
    
    //插入头尾
	StackPush(&st, left);
	StackPush(&st, right);

    //循环代替递归
	while (!StackEmpty(&st))
	{

        //因为后压的右下标,所以右下标先出来
		int right1 = StackTop(&st);
		StackPop(&st);
		int left1 = StackTop(&st);
		StackPop(&st);

        //对这一块空间排序
		int mid = PartSort2(a, left1, right1);

        //如果左边还有就压左边
		if (mid-1-left1>0)
		{
			StackPush(&st, left1);
			StackPush(&st, mid - 1);
		}

        //右边还有就压右边
		if (right1-mid-1>0)
		{
			StackPush(&st, mid + 1);
			StackPush(&st, right1);
		}
	}

    //排序完销毁栈
	StackDestroy(&st);
}

这里用的单趟快排上面可以复制,这里将不写了.

时间复杂度:O(N*logN)

空间复杂度:O(1)

挺快的,但代码很长...

------------

归并

如果做过这样的一道题,那归并的思路就很好理解了:

请合并两个有序数组,并让返回的数组依旧有序

先比较第一个数据

1 >  2  ?

新创建的数组的第一个元素就放小的那个,然后让 3 跟  2  比

2 小于 3 

所以新数组第二个元素就放 2 

然后 4 跟  3  比

.......

直到其中一个没有或者两个都比完:

这就叫归并

 那归并排序是什么样的呢?

看图:

这是已有的数组

对其中每一块区域分别归并:

 

以左半边举例

9  3  8  6 显然无序

将它分为9  3   一组 8   6

9  3 也无序,所以将其分为   9  一组,3一组

然后归并就变成了

3  9

8  6归并就成了6  8

再将3  9 和6  8归并

3  6  8  9 

递归的条件,即有多个元素,每次都分一半,直到没得分,这个时候就可以归并了

切记,归并不能在原数组归并,不然会丢失数据,所以要新建立一个临时数组,然后将这个数组的值拷贝进去

void _MergeSort(int*a, int begin, int end, int* tmp)
{

    //如果begin >= end  说明这个区间是无效区间,直接返回
	if (begin >= end)
		return;


    //每次都取一半
	int mid = (begin + end) / 2;

    //左半边
	_MergeSort(a, 0, mid, tmp);

    //右半边
	_MergeSort(a, mid+1, end, tmp);


    //单趟(归并没什么好说的吧?)
	int begin1 = begin ,  end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int pos = begin;

	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
			tmp[pos++] = a[begin1++];
		else
			tmp[pos++] = a[begin2++];
	}

    //也许是其中一个数组放完了,另一个还没有,所以判断一下
	while (begin1 <= end1)
		tmp[pos++] = a[begin1++];

	while (begin2 <= end2)
		tmp[pos++] = a[begin2++];


    //别忘了拷贝过去
	memcpy(a + begin, tmp + begin, (end - begin + 1)*sizeof(int));
}


// 归并排序递归实现
void MergeSort(int* a, int n)
{

    //新建立的临时数组,用于存放归并数组的数据
	int* tmp = (int*)malloc(sizeof(int)* n);
	assert(tmp);

    //调用归并函数
	_MergeSort(a, 0, n, tmp);

	free(tmp);
}

时间复杂度:O(N*logN)

空间复杂度:O(N)

不好用,别用

--------

非递归实现归并

非递归,就是模拟递归的一个过程

在递归实现里面,先将其中元素一个一个归并,然后再两个两个归并,再四个四个归并...

那是不是可以拿一个循环解决?

所以,非递归版本就这么来了:

首先要定义一个gap,这个gap是每次递归的区间

如果是1,每次就归并一个

如果是2,每次就归并两个

如果是4,每次就归并四个

...

每次都归并一个数组的长度,可以嵌套一个for循环

在定义两个数组的头尾指针

如果gap是1,预期的效果是每次比较1个,那头尾指针就该这么定义:

begin1 = 0,end1 = begin1+gap-1;

 begin1是从0开始的,如果循环比较,那这里应该赋值为i(循环)

end1 则是 begin1 加个gap(间隔),但是别忘了-1才是下标

begin2 则是 begin+gap,这样就跳过了begin1的数组

end2 则是 begin2+gap-1,同end1原理

...

在走过一遍之后,要将gap*2,这样就可以一次归并两个长度为2的数组

...

切记

可能越界,因为gap每次乘2,及有发生以下情况:

end1越界了,那直接修改end1 = n(长度)-1

begin2 越界,那此时就要修改begin2和end2,因为判断条件是begin2 <= end2,所以只需要让begin2>end2即可

end2越界,此时需要将end2修改为 n(长度)-1

void MergeSortNonR(int* a, int n)
{
	
	//间隔 gap
	int gap = 1;
	int* tmp = (int*)malloc(sizeof(int)*n);

    //如果间隔大于长度,就不用比了
	while (gap < n)
	{

        //每次都遍历一遍数组
		for (int i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 =i+2*gap - 1;

        

            //判断可能越界的值
			if (end1 >= n)
				end1 = n - 1;

			// begin2 越界,第二个区间不存在
			if (begin2 >= n)
			{
				begin2 = n;
				end2 = n - 1;
			}

			// begin2 ok, end2越界,修正end2即可
			if (begin2 < n && end2 >= n)
				end2 = n - 1;

            //这里完全是为了好看,如果报错这里可以看到每次的区间
			printf("%d %d %d %d\n", begin1, end1, begin2, end2);

            //归并
			int pos = begin1;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
					tmp[pos++] = a[begin1++];
				else
					tmp[pos++] = a[begin2++];
			}

			//也许是其中一个数组放完了,另一个还没有,所以判断一下
			while (begin1 <= end1)
				tmp[pos++] = a[begin1++];

			while (begin2 <= end2)
				tmp[pos++] = a[begin2++];


			//别忘了拷贝过去
			memcpy(a, tmp, sizeof(int)*end2);
		}

		gap = gap * 2;
	}

    //用完了释放,别忘记了
	free(tmp);
}

时间复杂度:O(N*logN)

空间复杂度:O(N)

不好用,别用

-------------

计数排序

一个比较简单的排序,如果理解的话,应该是这样理解的

这是要排序的数组,先建立一个数组,这个数组的大小应该是要排序里面数字的最大值

举个例子,这里最大的是9,所以就要开辟 10 个整型的空间(因为只有10个空间最后的下标才是9)

将待排序的数组元素作为下标,放到开辟空间对应的下标处,每放一个,就+1(初始化0)

打印的时候再将开辟数组里面不为0的地方打印出来

比方说这里有 2个3,那新开辟数组下标为3的位置就有 2 个,到时候返回就多返回一个

------

但是这样做有一个坏处,就是,如果用最大数字来开辟空间的话,那假设是这样的一个数组

10000 5000  9999   8888

最大值10000,也就是说要开辟10000个整型的空间,但前面4999个都用不到

于是就有了优化版本

以最小的为参考值

这里是5000

开辟空间时开辟 最大值-最小值+1的空间

放数据的时候再-一个最小值

再之后打印的时候再+最小值

比方说5000,它放进去的时候-5000,就会放到 0 的位置

打印的时候 0+ 5000,所以打印出来的就是5000

// 计数排序
void CountSort(int* a, int n)
{
    //找最大最小值
	int max, min;
	max = min = a[0];
	int i;
	for (i = 1; i < n; i++)
	{
		if (a[i] > max)
		{
			max = a[i];
		}
		if (a[i] < min)
		{
			min = a[i];
		}
	}

	//开辟空间
	int range = max - min + 1;
	int* arr = (int*)calloc(range, sizeof(int));
	assert(arr);

	//开始计数
	for (i = 0; i < n; i++)
	{
		arr[a[i]-min] +=1;
	}

	//放回原数组
	int j = 0;
	for (i = 0; i < range; i++)
	{
		while (arr[i]--)
		{
			a[j++] = i+min;
		}
	}
		
	//释放空间
	free(arr);
	arr = NULL;
}

时间复杂度:O(N+Range(数据范围)) 

空间复杂度:O(N+Range(数据范围))

适用于范围比较集中、数据量大的情况,如果类似 10000 1

还是不要用这种了

-------------

稳定性:

排序除了时间复杂度和空间复杂度以外,还有一个值得比较的是它的稳定性

稳定性可以用下图理解:

原本红色的99在黑的前面,现在排完序它们之间的相对位置还是没变,红的还是在黑的前面

上面的八个排序中:

1.插入排序:稳

每次移动一个,原本在前面的在移动后面的时候也不会变位

2.希尔排序:不稳

如果有两个同样的数据但被分到不一样的组,那之后调整就可以出问题

3.选择排序:不稳

3 3  1  1

假设原本是这样的,将1调整到第一位的时候,原本第一位的3会来到第三位,这样就会出问题

4.堆排序:不稳

堆排序建大堆小堆直接就乱了

5.冒泡排序:稳

每次都只是交换,前后位置还是不变的

6.快速排序:不稳

每次分割一半,兴许哪一次就出现问题

7.归并排序:稳(不稳)

如果两数一样时都放第一个数组元素,那它就是稳的,如果放第二个数组,那就是不稳的

8.计数排序:不稳

它只管计数,然后放回去,不会管先放的是哪个

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/723134.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-26
下一篇 2022-04-26

发表评论

登录后才能评论

评论列表(0条)