• 八大排序(下)

    文章目录

    一、快速排序

    1.挖坑法

    1.过程

    1.为了使用方便我们默认第一个数为key，key的值可以看作单独提出来了，key所在的(pivot)坑的位置
    先从右边开始找比key小的数，找到后将值传给pivot所在位置，同时pivot指向右边

    在这里插入图片描述

    2.再从左边找比key大的数，找到后将值传给左边pivot所在位置 ，同时pivot指向左边
    在这里插入图片描述

    3.当begin与end指向同一个位置时，则将关键字传入进去 ，循环结束
    在这里插入图片描述

    2.对于递归结束条件的分析

    在这里插入图片描述

    当递归到最后时，发现只剩下一个数或者没有数存在，
    而在循环中成立的条件为 lelft 当left==right时，只有一个数
    当left>right时，没有数存在

    3. 代码实现

    void swap(int* pa, int* pb)
{
	int tmp = 0;
	tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}
int getmid(int* a, int left, int right)//三数取中  为了防止有序时时间复杂度为O(N^2)
{
	int mid = (left + right) / 2;
	if (a[left] > a[mid])
	{
		if (a[right] > a[left])
		{
			return left;
		}
		else if (a[mid] > a[right])
		{
			return mid;
		}
		else
		{
			return right;
		}
	}
	else//a[left]  
	{
		if (a[right] < a[left])
		{
			return left;
		}
		else if (a[mid] < a[right])
		{
			return mid;
		}
		else
		{
			return right;
		}
	}
}
void   quicksort(int*a,int  left, int right )
{
	if (left >= right)//left==right时，只存在一个值，left>right时，区间不存在
	{
		return;
	}
	int index = getmid(a, left, right);
	swap(&a[left], &a[index]);//默认key的位置为左边第一个
	int begin = left;
	int end =  right;
	int pivot = begin;//pivot代表坑位
	int key = a[begin];
	while (begin < end)//一趟排序
	{
		while (a[end] >= key&&begin<end)//右边找小，放到左边
		{
			end--;
		}
		a[pivot] = a[end];//把小的放在左边的坑位中，自己形成新的坑位
		pivot = end;

		while (a[begin] <= key&&begin<end)//左边找大，放到右边
		{
			begin++;
		}
		a[pivot] = a[begin];//把大的放在右边的坑位中，自己形成新的坑位
		pivot = begin;
	}
	pivot = begin;//当begin==end时，循环结束，将关键字赋值给begin所在位置
	a[pivot] = key;//通过坑位分成两部分   [left    pivot-1] pivot [pivot+1   right]
	if (pivot - 1 - left > 10) //小区间优化
	{
		quicksort(a, left, pivot - 1);
	}
	else
	{
		insertsort(a + left, pivot - 1 - left+1);//随着递归的变化 ，左区间有可能不从0开始，右区间是下标变化要+1
	}
	if (right - (pivot + 1) > 10)
	{
		quicksort(a, pivot + 1, right);
	}
	else
	{
		insertsort(a + pivot+1, right - (pivot + 1)+1);
	}
	
	
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90

    4.快速排序的时间复杂度

    理想情况下，每次都用坑pivot 将left与right区间平分 即满二叉树
    在这里插入图片描述
    每一层都会将所有数遍历一遍，所有每一层的时间复杂度为O(N)
    一共遍历了高度次 根据二叉树性质：2^h-1=N h=log N
    快速排序的整体时间复杂度为O(N*logN)

    5.三数取中

    快排什么时候为最坏情况
    有序时最坏
    以顺序为列 ，每次只能选出一个数 此时的时间复杂度为O(N^2)
    在这里插入图片描述
    所以为了防止这种情况的发生，采用三数取中

    6.小区间优化

    使用小区间优化是为了减少函数调用的次数
    在这里插入图片描述
    当我们递归会发现最后几层的函数调用占据了绝大多数
    我们假设当一个区间内相差不超过10，就消除
    消除的部分则使用直接插入排序
    直接插入排序在这里:八大排序(上)

    2.左右指针法

    1.过程

    简单来说，就是先从右面找比关键字小的 ，再从左边找比关键字大的 ，两者交换，
    当left==right时，将此时的值与关键字交换
    在这里插入图片描述

    2.代码实现

    void swap(int* pa, int* pb)
{
	int tmp = 0;
	tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}
int  partsort(int* a, int left, int right)//左右指针法
{
	if (left >= right)
	{
		return;
	}
	int begin = left;
	int end = right;
	int key = left;
	while (begin < end)
	{
		while (a[end] >= a[key] && begin < end)
		{
			end--;
		}
		while (a[begin] <= a[key] && begin < end)
		{
			begin++;
		}
		swap(&a[begin], &a[end]);//当左边找到小的 ，右边找到大的时候 就将两者值交换
	}
	swap(&a[key], &a[begin]);
	return begin;    // [left ,begin-1] begin [begin+1,  right]
}


int getmid(int* a, int left, int right)//三数取中  为了防止有序时时间复杂度为O(N^2)
{
	int mid = (left + right) / 2;
	if (a[left] > a[mid])
	{
		if (a[right] > a[left])
		{
			return left;
		}
		else if (a[mid] > a[right])
		{
			return mid;
		}
		else
		{
			return right;
		}
	}
	else//a[left]  
	{
		if (a[right] < a[left])
		{
			return left;
		}
		else if (a[mid] < a[right])
		{
			return mid;
		}
		else
		{
			return right;
		}
	}
}
void   quicksort(int* a, int  left, int right)
{
	int keyindex = partsort(a,left, right);
	if (keyindex - 1 - left > 10)
	{
		quicksort(a, left, keyindex - 1);
	}
	else
	{
		insertsort(a + left, keyindex - 1 - left + 1);//随着递归的变化 ，左区间有可能不从0开始，右区间是下标变化要+1
	}
	if (right - (keyindex + 1) > 10)
	{
		quicksort(a, keyindex + 1, right);
	}
	else
	{
		insertsort(a + keyindex + 1, right - (keyindex + 1) + 1);
	}


}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89

    3.前后指针法

    1.过程

    1.当cur的值比key大时，cur++
    在这里插入图片描述

    2.当cur的值比key小时 ,prev++ ，并交换两者的值
    在这里插入图片描述

    3.当cur遍历完数组时，就将prev位置的值与key位置的值交换
    在这里插入图片描述

    2.代码实现

    void swap(int* pa, int* pb)
{
	int tmp = 0;
	tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}
int getmid(int* a, int left, int right)//三数取中  为了防止有序时时间复杂度为O(N^2)
{
	int mid = (left + right) / 2;
	if (a[left] > a[mid])
	{
		if (a[right] > a[left])
		{
			return left;
		}
		else if (a[mid] > a[right])
		{
			return mid;
		}
		else
		{
			return right;
		}
	}
	else//a[left]  
	{
		if (a[right] < a[left])
		{
			return left;
		}
		else if (a[mid] < a[right])
		{
			return mid;
		}
		else
		{
			return right;
		}
	}
}
int partsort(int* a, int left, int right)//前后指针法
{
	if (left >= right)
	{
		return 0;
	}
	int key = left;
	int prev = left;
	int cur = left + 1;
	while (cur <= right)
	{
		if (a[cur] < a[key] && ++prev != cur)//如果cur位置值比key位置值小 ，prev++ 并交换两者值
		{                                //如果prev向后移后的值与key位置值相等就不进入循环 没有交换的必要
			prev++;
			swap(&a[prev], &a[cur]);
		}
		cur++;

	}
	swap(&a[prev], &a[key]);//当cur出了right范围，将prev位置值与key位置值交换
	return prev;
}
void   quicksort(int* a, int  left, int right)
{
	int keyindex = partsort(a,left, right);
	if (keyindex - 1 - left > 10)
	{
		quicksort(a, left, keyindex - 1);
	}
	else
	{
		insertsort(a + left, keyindex - 1 - left + 1);//随着递归的变化 ，左区间有可能不从0开始，右区间是下标变化要+1
	}
	if (right - (keyindex + 1) > 10)
	{
		quicksort(a, keyindex + 1, right);
	}
	else
	{
		insertsort(a + keyindex + 1, right - (keyindex + 1) + 1);
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83

    4.非递归

    非递归借助了数据结构栈的模拟:栈和队列的实现

    1.过程

    在这里插入图片描述
    栈有先进后出的原则 ，所以我们先判断下是否符合区间值>1的条件，如果符合，则先将右边的右入栈，再入右边的左 ，其次入左边的右，再入，做左边的左
    呈现出来则为 ，左边的左 ，右 ，右边的左，右

    2.代码实现

    int   partsort(int* a, int  left, int right)
{
	if (left >= right)
	{
		return 0;
	}
	int begin = left;
	int end = right;
	int pivot = begin;
	int key = a[begin];
	while (begin < end)
	{
		while (a[end] >= key && begin < end)
		{
			end--;
		}
		a[pivot] = a[end];
		pivot = end;

		while (a[begin] <= key && begin < end)
		{
			begin++;
		}
		a[pivot] = a[begin];//把大的放在右边的坑位中，自己形成新的坑位
		pivot = begin;
	}
	pivot = begin;//当begin==end时，循环结束，将关键字赋值给begin所在位置
	a[pivot] = key;//通过坑位分成两部分   [left    pivot-1] pivot [pivot+1   right]
	return pivot;
}
void quicksortNonR(int* a, int n)
{
	ST st;
	stackinit(&st);
	stackpush(&st, n - 1);//先将右 输入  再将左输入
	stackpush(&st, 0);//输出时，则为左先输出 ，右再输出
	while (!stackempty(&st))
	{
		int left = stacktop(&st);
		stackpop(&st);
		int right = stacktop(&st);
		stackpop(&st);
		int keyindex = partsort(a, left, right);// [left    keyindex-1] keyindex [keyindex+1   right]
		if (keyindex + 1 < right)//栈符合先进后出的原则 
		{
			stackpush(&st, right);//先入右区间的右 再入右区间的左
			stackpush(&st, keyindex + 1);//输出右区间的左 再输出右
		}
		if (left < keyindex - 1)//再入左区间的右  左区间的左
		{
			stackpush(&st, keyindex - 1);//输出左区间的左，再输出右
			stackpush(&st, left);
		}

	}
	stackdestroy(&st);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57

    二、归并排序

    1.递归

    1.过程

    在这里插入图片描述

    通过递归的方式使左半区间与右半区间有序 ，最后使整体区间有序

    2.代码实现

    void mergesort(int* a, int left, int right, int* tmp)//
{
	if (left >= right)//当区间不存在或者只有一个时 返回
	{
		return;
	}
	int mid = (left + right) / 2;
	mergesort(a, left, mid, tmp);//左半区间
	mergesort(a, mid+1, right, tmp);//右半区间


	int begin1 = left;
	int end1 = mid;
	int begin2 = mid + 1;
	int end2 = right;
	int index = left;
	while (begin1 <= end1 && begin2 <= end2)//将小的的依次放入新的临时数组中
	{
		if (a[begin1] < a[begin2])
		{
			tmp[index] = a[begin1];
			index++;
			begin1++;
		}
		else
		{
			tmp[index] = a[begin2];
			index++;
			begin2++;
		}
	}
	while (begin1 <= end1)//如果此时的左区间未完全排完 则进入循环
	{
		tmp[index] = a[begin1];
		index++;
		begin1++;
	}
	while (begin2 <= end2)//如果此时的右区间未完全排完 则进入循环
	{
		tmp[index] = a[begin2];
		index++;
		begin2++;
	}
	int i = 0;
	for (i = 0; i <=right; i++)//将此时排好的临时数组传回原数组中
	{
		a[i] = tmp[i];
	}
}
void sort(int* a, int n)//归并排序  递归
{
	int left = 0;
	int right = n - 1;
	int* tmp = (int*)malloc(sizeof(int) * n);
	mergesort(a, left, right, tmp);
	free(tmp);
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58

    3.归并排序的时间复杂度

    在这里插入图片描述

    每次都分为 两个对半的区间
    可以看作是一个满二叉树
    2^h-1=N h=log N
    当向上递归排序时,每一层的区间排序会遍历到所有数 n
    时间复杂度为O(N)
    即归并排序整体时间复杂度为O(N*log N)

    4.递归的缺陷

    如果栈深度太深，栈的空间不够用，可能会造成溢出

    在这里插入图片描述

    2.非递归

    1.过程

    采用循环，从之前的底层开始进行，一直 到整体有序 结束
    假设此时数组中有8个数
    通过 [i ，i+gap-1] [i+gap ， i+2*gap-1] 每次都分为两个区间
    则gap为1时就将 左边区间个数为1 与右边区间个数为1 进行排序
    gap为2时就将 左边区间个数为2 与右边区间个数为2 进行排序
    gap为4时就将 左边区间个数为4 与右边区间个数为4 进行排序
    在这里插入图片描述

    2.代码实现

    void mergesortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	int gap = 1;
	int i = 0;
	while (gap < n)
	{
		for (i = 0; i < n; i += 2 * gap)//以gap为间隔 分为 1   2   4
		{
			int begin1 = i;//[i  i+gap-1] [i+gap   i+2*gap-1]
			int end1 = i + gap - 1;
			int begin2 = i + gap;
			int end2 = i + 2 * gap - 1;
			int index = i;
			if (begin2 >= n)//右区间可能不存在
			{
				break;
			}
			if (end2 >= n)//右区间算多了,修正下
			{
				end2 = n - 1;
			}
			while (begin1 <= end1 && begin2 <= end2)//排序
			{
				if (a[begin1] < a[begin2])
				{
					tmp[index] = a[begin1];
					index++;
					begin1++;
				}
				else
				{
					tmp[index] = a[begin2];
					index++;
					begin2++;
				}
			}
			while (begin1 <= end1)
			{
				tmp[index] = a[begin1];
				index++;
				begin1++;
			}
			while (begin2 <= end2)
			{
				tmp[index] = a[begin2];
				index++;
				begin2++;
			}
			int j = 0;
			for (j = i; j <=end2; j++)
			{
				a[j] = tmp[j];
			}
		}
		gap *= 2;
	}
	free(tmp);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59

    3.注意事项

    在这里插入图片描述
    左区间存在，右区间不存在时，左区间不需要归并

    在这里插入图片描述

    当将左区间的4个数 ，与右区间进行归并时
    发现右区间只有三个数，第4个数不存在，所以修正回第三个数作为end2

    当左区间的数不够gap所分的数，右区间不存在时，若将左区间拷贝回去会出现随机值
    所以进行归并的才拷贝回去，没有进行的就不需要拷贝 ,所以将返回过程放入循环中
    在这里插入图片描述

    三、计数排序

    1.思想

    1.统计数，与其下标的大小对应，观察每个下标所对应的数量，直接输出就排好序了 ，此时为绝对映射位置
    在这里插入图片描述

    2.若数字过大 ，前面的空间就会浪费掉，所以避免这种情况的发生，则进行相对位置的映射
    在这里插入图片描述

    2.代码实现

    时间复杂度为O(N)

    void countsort(int* a, int n)
{
	int i = 0;
	int j = 0;
	int max = a[0];
	int min = a[0];
	for (i = 0; i < n; i++)
	{
		if (max < a[i])
		{
			max = a[i];
		}
		if (min > a[i])
		{
			min = a[i];
		}
	}
	int range = max - min+1;//从0开始 所以多了一个数    
	int* count = (int*)malloc(sizeof(int) * range);
	memset(count, 0, sizeof(int) * range);//将count都初始化为0
	for (i = 0; i < n; i++)//统计次数
	{
		count[a[i] - min]++;//a[i]-min为相对映射位置
	}
	for (i = 0; i < range; i++)//遍历 下标范围
	{
		while (count[i]--)//判断每个下标中的次数
		{
			a[j] = i+min;
			j++;
		}
	}
	free(count);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
  • 相关阅读:
    【信号处理】Matlab实现希尔伯特-黄变换
    查看数据库数据量大小，占用磁盘大小
    MySQL索引的数据结构
    Flask 使用 JWT（二）
    什么是模型
    （二）前端开发面试会问到的问题有哪些？
    linux下部署darknet
    (☞ﾟヮﾟ)☞【精品C语言整理】☜(ﾟヮﾟ☜)女盆友缠着你让你教她写代码怎么办？安排，三万字博文带你走遍C语言，从此不再害怕编程
    Node-怎么连接MySQL
    DNA脱氧核糖核酸修饰金属铂纳米颗粒PtNPS-DNA|科研试剂
  • 原文地址：https://blog.csdn.net/qq_62939852/article/details/126676861