• 【数据结构】排序--快速排序

    目录

    一 概念

    二 快速排序的实现

    1. hoare版本

    (1)代码实现

    (2)单趟排序图解

    (3) 递归实现图解

    (4)细节控制

    (5)时间复杂度

    (6)三数取中优化

    2 挖坑法

    (1)代码实现

    (2)单趟图解 

    3 前后指针法 

    (1) 代码实现 

    (2) 单趟图解

    ​4 优化子区间 

    5 非递归快速排序

    ​ 三 快速排序的特性总结

    一 概念

    快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中 的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右 子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止

    二 快速排序的实现

    上述为快速排序递归实现的主框架，发现与二叉树前序遍历规则非常像

    1. hoare版本

    (1)代码实现

    1. #include
    2. void Swap(int* x, int* y)
    3. {
    4. 	int tmp = *x;
    5. 	*x = *y;
    6. 	*y = tmp;
    7. }
    8.  
    9. int PartSort1(int* a, int left, int right)
    10. {
    11. 	int keyi = left;
    12. 	while (left < right)
    13. 	{
    14. 		//找小
    15. 		while (left < right && a[right] >= a[keyi])
    16. 		{
    17. 			right--;
    18. 		}
    19.  
    20. 		//找大
    21. 		while (left < right && a[left] <= a[keyi])
    22. 		{
    23. 			left++;
    24. 		}
    25.  
    26. 		Swap(&a[left], &a[right]);
    27. 	}
    28. 	Swap(&a[keyi], &a[left]);
    29. 	return left;
    30. }
    31.  
    32.  
    33. void QuickSort(int* a, int begin, int end)
    34. {
    35. 	if (begin >= end)
    36. 	{
    37. 		return;
    38. 	}
    39. 	int key = PartSort1(a, begin, end);
    40. 	QuickSort(a, begin, key - 1);
    41. 	QuickSort(a, key + 1, end);
    42. }
    43. int main()
    44. {
    45. 	int arr[] = {6,1,2,7,9,3,4,5,10,8};
    46. 	QuickSort(arr, 0, (sizeof(arr) / sizeof(int)) - 1);
    47. 	for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
    48. 	{
    49. 		printf("%d ", arr[i]);
    50. 	}
    51. }

    (2)单趟排序图解

    我们看看单趟排序怎么排的

     

    (3) 递归实现图解

    再来看看递归怎么实现的

     

    (4)细节控制

    对细节控制上 我要做一下解释

     那这里相遇位置一定比a[keyi]小呢?  右边先走导致的

    (5)时间复杂度

    我们来算一下快速排序的时间复杂度(需要对二叉树的基本性质熟悉)

     

    (6)三数取中优化

    那针对有序 的情况 我们可以采取三数取中的方式解决

    1. #include
    2. void Swap(int* x, int* y)
    3. {
    4. 	int tmp = *x;
    5. 	*x = *y;
    6. 	*y = tmp;
    7. }
    8.  
    9. int GetMidi(int* a, int left, int right)
    10. {
    11. 	int mid = (left + right) / 2;
    12. 	if (a[left] < a[mid])
    13. 	{
    14. 		if (a[mid] < a[right])
    15. 		{
    16. 			return mid;
    17. 		}
    18.  
    19. 		else if (a[left] > a[right])
    20. 		{
    21. 			return left;
    22. 		}
    23. 		else
    24. 		{
    25. 			return right;
    26. 		}
    27. 	}
    28.  
    29. 	else// a[left] > a[mid]
    30. 	{
    31. 		if (a[left] < a[right])
    32. 		{
    33. 			return left;
    34. 		}
    35. 		else if (a[mid] > a[right])
    36. 		{
    37. 			return mid;
    38. 		}
    39. 		else
    40. 		{
    41. 			return right;
    42. 		}
    43. 	}
    44. }
    45.  
    46. int PartSort1(int* a, int left, int right)
    47. {
    48. 	int midi = GetMidi(a, left, right);
    49. 	Swap(&a[midi], &a[left]);
    50. 	int keyi = left;
    51. 	while (left < right)
    52. 	{
    53. 		//找小
    54. 		while (left < right && a[right] >= a[keyi])
    55. 		{
    56. 			right--;
    57. 		}
    58.  
    59. 		//找大
    60. 		while (left < right && a[left] <= a[keyi])
    61. 		{
    62. 			left++;
    63. 		}
    64.  
    65. 		Swap(&a[left], &a[right]);
    66. 	}
    67. 	Swap(&a[keyi], &a[left]);
    68. 	return left;
    69. }
    70.  
    71.  
    72. void QuickSort(int* a, int begin, int end)
    73. {
    74. 	if (begin >= end)
    75. 	{
    76. 		return;
    77. 	}
    78. 	int key = PartSort1(a, begin, end);
    79. 	QuickSort(a, begin, key - 1);
    80. 	QuickSort(a, key + 1, end);
    81. }
    82. int main()
    83. {
    84. 	int arr[] = {6,1,2,7,9,3,4,5,10,8};
    85. 	QuickSort(arr, 0, (sizeof(arr) / sizeof(int)) - 1);
    86. 	for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
    87. 	{
    88. 		printf("%d ", arr[i]);
    89. 	}
    90. }

     2 挖坑法

      (1)代码实现

    1. #include
    2. void Swap(int* x, int* y)
    3. {
    4. 	int tmp = *x;
    5. 	*x = *y;
    6. 	*y = tmp;
    7. }
    8.  
    9. int GetMidi(int* a, int left, int right)
    10. {
    11. 	int mid = (left + right) / 2;
    12. 	if (a[left] < a[mid])
    13. 	{
    14. 		if (a[mid] < a[right])
    15. 		{
    16. 			return mid;
    17. 		}
    18.  
    19. 		else if (a[left] > a[right])
    20. 		{
    21. 			return left;
    22. 		}
    23. 		else
    24. 		{
    25. 			return right;
    26. 		}
    27. 	}
    28.  
    29. 	else// a[left] > a[mid]
    30. 	{
    31. 		if (a[left] < a[right])
    32. 		{
    33. 			return left;
    34. 		}
    35. 		else if (a[mid] > a[right])
    36. 		{
    37. 			return mid;
    38. 		}
    39. 		else
    40. 		{
    41. 			return right;
    42. 		}
    43. 	}
    44. }
    45.  
    46.  
    47. int PartSort2(int* a, int left, int right)
    48. {
    49. 	int midi = GetMidi(a, left, right);
    50. 	Swap(&a[left], &a[midi]);
    51.  
    52. 	int key = a[left];
    53. 	//保存key值以后 左边形成第一个坑位
    54. 	int hole = left;
    55.  
    56. 	while (left < right)
    57. 	{
    58. 		//右边先走，找小，填到左边的坑，右边形成新的坑位
    59. 		if (left < right && a[right] >= key)
    60. 		{
    61. 			right--;
    62. 		}
    63.  
    64. 		a[hole] = a[right];
    65. 		hole = right;
    66.  
    67. 		//左边再走，找大，填到右边的坑，左边形成新的坑位
    68. 		if (left < right && a[left] <= key)
    69. 		{
    70. 			left++;
    71. 		}
    72. 		a[hole] = a[left];
    73. 		hole = left;
    74. 	}
    75. 	a[hole] = key;
    76. 	return hole;
    77. }
    78.  
    79. void QuickSort(int* a, int begin, int end)
    80. {
    81. 	if (begin >= end)
    82. 	{
    83. 		return;
    84. 	}
    85. 	int key = PartSort2(a, begin, end);
    86. 	QuickSort(a, begin, key - 1);
    87. 	QuickSort(a, key + 1, end);
    88. }
    89. int main()
    90. {
    91. 	int arr[] = {6,1,2,7,9,3,4,5,10,8};
    92. 	QuickSort(arr, 0, (sizeof(arr) / sizeof(int)) - 1);
    93. 	for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
    94. 	{
    95. 		printf("%d ", arr[i]);
    96. 	}
    97. }

    (2)单趟图解 

    3 前后指针法 

    (1) 代码实现 

    1. int PartSort3(int* a, int left, int right)
    2. {
    3. 	int keyi = left;
    4. 	int prev = left;
    5. 	int cur = prev + 1;
    6. 	while (cur <= right)
    7. 	{
    8. 		if (a[cur] < a[keyi] && ++prev != cur)
    9. 		{
    10. 			Swap(&a[cur], &a[prev]);
    11. 		}
    12. 		cur++;
    13. 	}
    14. 	Swap(&a[keyi], &a[prev]);
    15. 	return prev;
    16. }
    17. void QuickSort(int* a, int begin, int end)
    18. {
    19. 	if (begin >= end)
    20. 	{
    21. 		return;
    22. 	}
    23. 	int key = PartSort3(a, begin, end);
    24. 	QuickSort(a, begin, key - 1);
    25. 	QuickSort(a, key + 1, end);
    26. }
    27. int main()
    28. {
    29. 	int arr[] = {6,1,2,7,9,3,4,5,10,8};
    30. 	QuickSort(arr, 0, (sizeof(arr) / sizeof(int)) - 1);
    31. 	for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
    32. 	{
    33. 		printf("%d ", arr[i]);
    34. 	}
    35. }

    (2) 单趟图解

    4 优化子区间 

    递归到小的子区间时, 不在递归分割排序,可以考虑使用插入排序

    因为区间比较小的时候节点数开的很多  特别是最后一层 节点数占了整个数大致百分之五十

     

    1. int PartSort(int* a, int left, int right)
    2. {
    3. 	int midi = GetMidi(a, left, right);
    4. 	Swap(&a[left], &a[midi]);
    5.  
    6.  
    7. 	int keyi = left;
    8. 	int prev = left;
    9. 	int cur = prev + 1;
    10. 	while (cur <= right)
    11. 	{
    12. 		if (a[cur] < a[keyi] && ++prev != cur)
    13. 		{
    14. 			Swap(&a[cur], &a[prev]);
    15. 		}
    16. 		cur++;
    17. 	}
    18. 	Swap(&a[prev], &a[keyi]);
    19. 	return prev;
    20. }
    21.  
    22.  
    23.  
    24. void QuickSort(int* a, int begin, int end)
    25. {
    26. 	if (begin >= end)
    27. 	{
    28. 		return;
    29. 	}
    30.  
    31. 	if ((end - begin + 1) > 10)
    32. 	{
    33. 		int keyi = PartSort(a, begin, end);
    34. 		QuickSort(a, begin, keyi - 1);
    35. 		QuickSort(a, keyi + 1, end);
    36. 	}
    37. 	else
    38. 	{
    39. 		//插入排序
    40. 		InsertSort(a + begin, end - begin + 1);
    41. 	}
    42. }

    5 非递归快速排序

    需要有对栈的基础  不会的可以看前面的博客

    1. #include
    2. #include
    3. #include
    4. #include
    5. typedef struct STList
    6. {
    7. 	int* a;
    8. 	int size;
    9. 	int capacity;
    10. }ST;
    11.  
    12. void STInit(ST* ps)
    13. {
    14. 	assert(ps);
    15. 	ps->a = NULL;
    16. 	ps->size = ps->capacity = 0;
    17. }
    18.  
    19. void STDestroy(ST* ps)
    20. {
    21. 	assert(ps);
    22. 	free(ps->a);
    23. 	ps->a = NULL;
    24. 	ps->size = ps->capacity = 0;
    25. }
    26. void STPush(ST* ps, int x)
    27. {
    28. 	assert(ps);
    29. 	if (ps->size == ps->capacity)
    30. 	{
    31. 		int newcapacity = (ps->capacity == 0 ? 4 : ps->capacity * 2);
    32. 		int* tmp = (int*)realloc(ps->a, sizeof(int) * newcapacity);
    33. 		if (tmp == NULL)
    34. 		{
    35. 			perror("realloc fail");
    36. 			exit(-1);
    37. 		}
    38. 		ps->a = tmp;
    39. 		ps->capacity = newcapacity;
    40. 	}
    41. 	ps->a[ps->size] = x;
    42. 	ps->size++;
    43. }
    44.  
    45. void STPop(ST* ps)
    46. {
    47. 	assert(ps);
    48. 	assert(ps->size > 0);
    49. 	ps->size--;
    50. }
    51.  
    52. bool STEmpty(ST* ps)
    53. {
    54. 	assert(ps);
    55. 	return ps->size == 0;
    56. }
    57.  
    58. int STTop(ST* ps)
    59. {
    60. 	assert(ps);
    61. 	assert(ps->size > 0);
    62. 	return ps->a[ps->size - 1];
    63. }
    64. void Swap(int* x, int* y)
    65. {
    66. 	int tmp = *x;
    67. 	*x = *y;
    68. 	*y = tmp;
    69. }
    70.  
    71. int GetMidi(int* a, int left, int right)
    72. {
    73. 	int mid = (left + right) / 2;
    74. 	if (a[left] < a[mid])
    75. 	{
    76. 		if (a[mid] < a[right])
    77. 		{
    78. 			return mid;
    79. 		}
    80.  
    81. 		else if (a[left] > a[right])
    82. 		{
    83. 			return left;
    84. 		}
    85. 		else
    86. 		{
    87. 			return right;
    88. 		}
    89. 	}
    90.  
    91. 	else// a[left] > a[mid]
    92. 	{
    93. 		if (a[left] < a[right])
    94. 		{
    95. 			return left;
    96. 		}
    97. 		else if (a[mid] > a[right])
    98. 		{
    99. 			return mid;
    100. 		}
    101. 		else
    102. 		{
    103. 			return right;
    104. 		}
    105. 	}
    106. }
    107.  
    108. int PartSort(int* a, int left, int right)
    109. {
    110. 	int midi = GetMidi(a, left, right);
    111. 	Swap(&a[left], &a[midi]);
    112.  
    113.  
    114. 	int keyi = left;
    115. 	int prev = left;
    116. 	int cur = prev + 1;
    117. 	while (cur <= right)
    118. 	{
    119. 		if (a[cur] < a[keyi] && ++prev != cur)
    120. 		{
    121. 			Swap(&a[cur], &a[prev]);
    122. 		}
    123. 		cur++;
    124. 	}
    125. 	Swap(&a[prev], &a[keyi]);
    126. 	return prev;
    127. }
    128.  
    129.  
    130.  
    131. void QuickSortNonR(int* a, int begin, int end)
    132. {
    133. 	ST st;//创建一个栈 
    134. 	STInit(&st);//初始化
    135. 	STPush(&st, end);
    136. 	STPush(&st, begin);
    137. 	while (!STEmpty(&st))
    138. 	{
    139. 		int left = STTop(&st);
    140. 		STPop(&st);
    141.  
    142. 		int right = STTop(&st);
    143. 		STPop(&st);
    144.  
    145. 		int keyi = PartSort(a, left, right);
    146. 		// [lefy,keyi-1] keyi [keyi+1, right]
    147. 		if (keyi + 1 < right)
    148. 		{
    149. 			STPush(&st, right);
    150. 			STPush(&st, keyi + 1);
    151. 		}
    152.  
    153. 		if (left < keyi - 1)
    154. 		{
    155. 			STPush(&st, keyi - 1);
    156. 			STPush(&st, left);
    157. 		}
    158. 	}
    159.  
    160. 	STDestroy(&st);
    161. }
    162.  
    163. int main()
    164. {
    165. 	int arr[] = {6,1,2,7,9,3,4,5,10,8};
    166. 	QuickSortNonR(arr, 0, (sizeof(arr) / sizeof(int)) - 1);
    167. 	for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
    168. 	{
    169. 		printf("%d ", arr[i]);
    170. 	}
    171. }

     三 快速排序的特性总结

    1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序

    2. 时间复杂度：O(N*logN)

    3. 空间复杂度：O(logN)

    4. 稳定性：不稳定

    本节难度还是不低, 但是我觉得大家根据图解和代码慢慢吃透还是不难的,这节我画的图解很多, 对重点和难点进行了很细致的划分和讲解, 希望大家可以窥探到快速排序的妙处

    继续加油!

  • 相关阅读:
    你觉得好的代码可能并不是最优的解决方案
    企业电子招标采购系统源码Spring Boot + Mybatis + Redis + Layui + 前后端分离 构建企业电子招采平台之立项流程图
    浅谈系统架构中的状态
    下载 Windows11 23H2 官方系统镜像
    四十二、《大数据项目实战之用户行为分析》多框架整合实时分析用户行为日志数据流
    (翻译) CAP 理论 FAQ
    一台机器下，多个Java版本的粗放与精细管理
    无线通信模块定点传输-点对多点的具体传输应用
    JVM——10.对象的内存布局
    Leetcode652. 寻找重复的子树
  • 原文地址：https://blog.csdn.net/yf214wxy/article/details/133828137