• 数据结构——排序

    目录

    插入排序

    希尔排序 

    选择排序 

    交换排序 

    冒泡排序 

    快速排序 

    hoare版本 

     挖坑法

     前后指针法

     非递归

    给大家推荐一款刷题，找工作的好网站——牛客网

    牛客网 - 找工作神器|笔试题库|面试经验|实习招聘内推，求职就业一站解决_牛客网

     

    插入排序

     思路（这里以升序为例）：

    1.先用一个变量接收最后一个元素，这里是tmp

    2.用tmp保存的元素与前面的进行比较，如果比前面小则把前面的覆盖到end+1的位置

    3.覆盖之后end继续向前走，end+1，自然也跟着向前走，此时可以看到tmp的作用，就是保存最后一个元素

    4.当end<0时，一轮比较结束，此时将tmp的值传给end+1，即队首的位置，还有一种情况可使一轮比较结束

    当end位置的元素 

    1. void InsertSort(int* a, int n)
    2. {
    3. 	int end = n - 1;
    4. 	int tmp = a[end + 1];
    5. 	for (int i = 0; i < n-1; i++)
    6. 	{
    7. 		end = i;
    8. 		tmp = a[end + 1];
    9. 		while (end >= 0)
    10. 		{
    11. 			if (a[end] > tmp)
    12. 			{
    13. 				a[end + 1] = a[end];
    14. 				end--;
    15. 			}
    16. 			else
    17. 				break;
    18. 		}
    19. 		a[end + 1] = tmp;
    20. 	}
    21.  
    22. }
    23. int main()
    24. {
    25. 	int arr[] = {9,8,7,6,5,4,3,2,1,0 };
    26. 	int n = sizeof(arr) / sizeof(arr[0]);
    27. 	InsertSort(arr, n);
    28. 	return 0;
    29. }

     直接排序时间复杂度：O(N^2)

    希尔排序 

    1.预排序：接近有序，将间隔为gap的数据分成一组

    设置一个gap将数组分为几组，这里gap是3，将数组分为了3组

    9 5 8 5一组，1 7 6一组，2 4 3 一组

     

    我们先将第一个红色部分的进行排序，我们可以看到红色部分是按照升序的

    1. void ShellSort(int* a, int n)
    2. {
    3. 	int gap = 3;
    4. 	int end = n - 1;
    5. 	int tmp = a[end + gap];
    6. 	for (int i = 0; i < n-gap; i+=gap)
    7. 	{
    8. 		end = i;
    9. 		tmp = a[end + gap];
    10. 		while (end >= 0)
    11. 		{
    12. 			if (a[end] > tmp)
    13. 			{
    14. 				a[end + gap] = a[end];
    15. 				end=end-gap;
    16. 			}
    17. 			else
    18. 				break;
    19. 		}
    20. 		a[end + gap] = tmp;
    21. 	}
    22.  
    23. }
    24. int main()
    25. {
    26. 	int arr[] = {9,1,2,5,7,4,8,6,3,5 };
    27. 	int n = sizeof(arr) / sizeof(arr[0]);
    28. 	InsertSort(arr, n);
    29. 	return 0;
    30. }

     2.对3个组分别进行排序，使这三个部分有序

    1. void ShellSort(int* a, int n)
    2. {
    3. 	int gap = 3;
    4. 	for (int j = 0; j < gap; ++j)
    5. 	{
    6. 		for (int i = j; i < n - gap; i += gap)
    7. 		{
    8. 			int end = i;
    9. 			int tmp = a[end + gap];
    10. 			while (end >= 0)
    11. 			{
    12. 				if (a[end] > tmp)
    13. 				{
    14. 					a[end + gap] = a[end];
    15. 					end -= gap;
    16. 				}
    17. 				else
    18. 				{
    19. 					break;
    20. 				}
    21. 			}
    22. 			a[end + gap] = tmp;
    23. 		}
    24. 	}
    25. }
    26. int main()
    27. {
    28. 	int arr[] = {9,1,2,5,7,4,8,6,3,5 };
    29. 	int n = sizeof(arr) / sizeof(arr[0]);
    30. 	ShellSort(arr, n);
    31. 	return 0;
    32. }

    也可以这样

    1. void ShellSort(int* a, int n)
    2. {
    3. 	int gap = 3;
    4. 		for (int i = 0; i < n - gap; i ++)
    5. 		{
    6. 			int end = i;
    7. 			int tmp = a[end + gap];
    8. 			while (end >= 0)
    9. 			{
    10. 				if (a[end] > tmp)
    11. 				{
    12. 					a[end + gap] = a[end];
    13. 					end -= gap;
    14. 				}
    15. 				else
    16. 				{
    17. 					break;
    18. 				}
    19. 			}
    20. 			a[end + gap] = tmp;
    21. 		}
    22. }
    23. int main()
    24. {
    25. 	int arr[] = {9,1,2,5,7,4,8,6,3,5 };
    26. 	int n = sizeof(arr) / sizeof(arr[0]);
    27. 	ShellSort(arr, n);
    28. 	return 0;
    29. }

    3.对整体进行排序 

    1. void ShellSort(int* a, int n)
    2. {
    3. 	int gap = n;
    4. 	while (gap > 1)
    5. 	{
    6. 		gap = gap / 3 + 1;//或gap=gap/2;
    7. 		for (int i = 0; i < n - gap; i++)
    8. 		{
    9. 			int end = i;
    10. 			int tmp = a[end + gap];
    11. 			while (end >= 0)
    12. 			{
    13. 				if (a[end] > tmp)
    14. 				{
    15. 					a[end + gap] = a[end];
    16. 					end -= gap;
    17. 				}
    18. 				else
    19. 				{
    20. 					break;
    21. 				}
    22. 			}
    23. 			a[end + gap] = tmp;
    24. 		}
    25. 	}
    26. }
    27. int main()
    28. {
    29. 	int arr[] = {9,1,2,5,7,4,8,6,3,5 };
    30. 	int n = sizeof(arr) / sizeof(arr[0]);
    31. 	ShellSort(arr, n);
    32. 	return 0;
    33. }

    当gap是1的时候是直接排序，其余情况是预排序

    希尔排序时间复杂度：O(N^1.3)

    数据结构排序算法
    pdf 0星 超过10%的资源 561KB
    下载

    选择排序 

    1. // 最坏时间复杂度：O(N^2)
    2. // 最好时间复杂度：O(N^2)
    3. void SelectSort(int* a, int n)
    4. {
    5. 	int begin = 0, end = n - 1;
    6. 	while (begin < end)
    7. 	{
    8. 		// 选出最小的放begin位置
    9. 		// 选出最大的放end位置
    10. 		int mini = begin, maxi = begin;
    11. 		for (int i = begin + 1; i <= end; ++i)
    12. 		{
    13. 			if (a[i] > a[maxi])
    14. 			{
    15. 				maxi = i;
    16. 			}
    17.  
    18. 			if (a[i] < a[mini])
    19. 			{
    20. 				mini = i;
    21. 			}
    22. 		}
    23.  
    24. 		Swap(&a[begin], &a[mini]);
    25. 		// 修正一下maxi
    26. 		if (maxi == begin)       //如果没有这条语句，当最大数是首元素时，前面语句会把最小的元素换到首元素，而此时maxi指向首元素，首元素却不是最大值，后面再交换就会出错
    27. 			maxi = mini;
    28.  
    29. 		Swap(&a[end], &a[maxi]);
    30. 		++begin;
    31. 		--end;
    32. 	}
    33. }

     1.一开始让maxi 和 mini 为数组首元素的下标

    2. 接着遍历数组，进行比较替换

    直接选择排序最慢的排序之一

    选择排序的时间复杂度不像前面几种排序方法那样，前面几种排序方法的时间复杂度不是一眼就能看出来的，而是要通过推导计算才能得到的。一般会涉及到递归和完全二叉树，所以推导也不是那么容易。但是选择排序就不一样了，你可以很直观的看出选择排序的时间复杂度：就是两个循环消耗的时间；
           比较时间：T = （n-1)）+ （n -2）+（n - 3）.... + 1;  ===>>  T =  [n*(n-1) ] / 2；
          交换时间：最好的情况全部元素已经有序，则 交换次数为0；最差的情况，全部元素逆序，就要交换 n-1 次；
           所以最优的时间复杂度  和最差的时间复杂度   和平均时间复杂度  都为 ：O(n^2)

    2.使用选择排序对长度为100的数组进行排序，则比较的次数为（ ）

    A.5050

    B.4950

    C.4851

    D.2475

    答案：B

    解析：

    选择排序，每次都要在未排序的所有元素中找到最值，

    如果有n个元素，则

    第一次比较次数： n - 1

    第二次比较次数： n - 2

    ....

    第n - 1次比较次数： 1

    所有如果n = 100

    则比较次数的总和：99 + 98 + ...... + 1

    共4950次。

    交换排序 

    冒泡排序 

    1. void BubbleSort(int* a, int n)
    2. {
    3. 	for (int j = 0; j < n; ++j)
    4. 	{
    5. 		int exchange = 0;
    6. 		for (int i = 1; i < n - j; ++i)
    7. 		{
    8. 			if (a[i - 1] > a[i])
    9. 			{
    10. 				Swap(&a[i - 1], &a[i]);
    11. 				exchange = 1;
    12. 			}
    13. 		}
    14. 		if (exchange == 0)
    15. 		{
    16. 			break;
    17. 		}
    18. 	}
    19. }

     

    比较集中排序，这里十万个数据，冒泡排序很慢

    冒泡排序：最坏情况时间复杂度：O(N^2),最好情况O(N)

    快速排序 

    hoare版本 

    1.设置最左边（或最右边）一个值为key，把比key小的key的放在key左边，大于key的放在key右边，这里key是6

     2.如何保证相遇位置比key要小，让R先走即可，这种情况是让左边第一个做key，同理右边第一个做key，让L先走，即可在小于K处相遇

    3.相遇之后交换相遇位置的数和key所指的数即可

    1.  
    2. int PartSort(int* arr, int left, int right)
    3. {
    4. 	int keyi = left;
    5. 	while (left < right)
    6. 	{
    7. 		while (left < right && arr[right] >= arr[keyi])//left
    8. 		{
    9. 			right--;
    10. 		}
    11. 		while (left < right && arr[left] <= arr[keyi])
    12. 		{
    13. 			left++;
    14. 		}
    15. 		
    16. 		if (left
    17. 			Swap(&arr[left], &arr[right]);
    18. 	}
    19. 	int meeti = left;
    20. 	Swap(&arr[meeti], &arr[keyi]);
    21. 	return meeti;
    22. }

    单趟排序

     要对所有数据排序，进行递归即可

    如何递归？

    将keyi左边先递归排序，然后再右边

    1.  
    2. int PartSort(int* arr, int left, int right)
    3. {
    4. 	int keyi = left;
    5. 	while (left < right)
    6. 	{
    7. 		while (left < right && arr[right] >= arr[keyi])//left
    8. 		{
    9. 			right--;
    10. 		}
    11. 		while (left < right && arr[left] <= arr[keyi])
    12. 		{
    13. 			left++;
    14. 		}
    15. 		
    16. 		if (left
    17. 			Swap(&arr[left], &arr[right]);
    18. 	}
    19. 	int meeti = left;
    20. 	Swap(&arr[meeti], &arr[keyi]);
    21. 	return meeti;
    22. }
    23. //部分排序
    24. void QuickSort(int* a, int begin, int end)
    25. {
    26. 	if (begin >= end)
    27. 	{
    28. 		return; //如果左指针>=右指针，返回
    29. 	}
    30. 	int keyi=PartSort(a, begin, end);
    31. 	QuickSort(a, begin, keyi - 1);//
    32. 	QuickSort(a, keyi+1, end);
    33. }
    34. //快排
    35. int main()
    36. {
    37. 	int arr[] = {9,1,2,5,7,4,8,6,3,5 };
    38. 	int n = sizeof(arr) / sizeof(arr[0]);
    39. 	QuickSort(arr, 0, n - 1);
    40. 	return 0;
    41. }

    当每次选key为中间值时，递归深度：logN，每次单趟排序合计起来个数是N，时间复杂度：O(N*logN)。 

    快排比堆排，希尔排序略胜一筹 

    单趟排序，如果选中间做key，如果还有一个大小为key的值在key的左边或右边，就不好搞。

    如果有序/接近有序，选左边排序，比key大的在左边，没有比key小的，key的左边为空，之后递归右边

     

    如果这样一直往下走，树的高度是N，每次递归都会少一个数

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

     debug,N=10000,就会栈溢出，此时换realse（100000个数据）版本看O(N^2)情况下的运算情况

    100W个数据

     优化选key逻辑：1.随机选一个位置做key（如果每次选最左边或最右边有可能会发生跟上面O(N^2)一样的情况，但如果随机选位置就算有序，每次选的数不一定是最左边或最右边）

                                 2.针对有序情况，选正中间的值做key，之后把key和最左边或最右边的交换即可

                                3.三数取中，第一个位置，中间位置，和最后一个位置，选出这三个位置上的中间数据值，然后再跟最左边数据交换

    1. void Swap(int* p1, int* p2)
    2. {
    3. 	int tmp = *p1;
    4. 	*p1 = *p2;
    5. 	*p2 = tmp;
    6. }
    7. int GetMindIndex(int* arr, int left, int right)
    8. {
    9. 	int mid = (right + left) / 2;
    10. 	if (arr[left] < arr[mid])
    11. 	{
    12. 		if (arr[mid] < arr[right])
    13. 			return mid;
    14. 		else if (arr[right]
    15. 			return left;
    16. 		else
    17. 			return right;
    18. 	}
    19. 	else
    20. 	{
    21. 		if (arr[mid] > arr[right])
    22. 			return mid;
    23. 		else if (arr[right] > arr[left])
    24. 			return left;
    25. 		else
    26. 			return right;
    27. 	}
    28. }
    29. int PartSort(int* arr, int left, int right)
    30. {
    31. 	int mid = GetMindIndex(arr, left, right);
    32. 	Swap(&arr[mid], &arr[left]);
    33. 	int keyi = left;
    34. 	while (left < right)
    35. 	{
    36. 		while (left < right && arr[right] >= arr[keyi])//left
    37. 		{
    38. 			right--;
    39. 		}
    40. 		while (left < right && arr[left] <= arr[keyi])
    41. 		{
    42. 			left++;
    43. 		}
    44. 		
    45. 		if (left
    46. 			Swap(&arr[left], &arr[right]);
    47. 	}
    48. 	int meeti = left;
    49. 	Swap(&arr[meeti], &arr[keyi]);
    50. 	return meeti;
    51. }
    52. void QuickSort(int* a, int begin, int end)
    53. {
    54. 	if (begin >= end)
    55. 	{
    56. 		return;
    57. 	}
    58. 	int keyi = PartSort(a, begin, end);
    59. 	QuickSort(a, begin, keyi - 1);//
    60. 	QuickSort(a, keyi + 1, end);
    61. }
    62. int main()
    63. {
    64. 	int arr[] = { 9,1,2,5,7,4,8,6,3,5 };
    65. 	int n = sizeof(arr) / sizeof(arr[0]);
    66. 	QuickSort(arr, 0, n - 1);
    67. 	return 0;
    68. }

    测试1000W个数据

    跟上面O(N^2)的相比，提高了不少，不用害怕栈溢出，因为其深度不会太深 ，深度是logN

    小区间优化

    倒数三层合计占用80%栈帧 

    这种形态有点像二叉树，最后一层占了一半的调用次数，每次调用就会开辟栈帧，如果倒数第二层有8个数进行排序，则要开辟三层栈帧， 8个值本身就是小范围，调用三层栈帧，调用7-8次递归，比较浪费栈帧空间。付出的代价太大

    因此当数据<=8时，我们用插入排序，其余用快排

    1. void Swap(int* p1, int* p2)
    2. {
    3. 	int tmp = *p1;
    4. 	*p1 = *p2;
    5. 	*p2 = tmp;
    6. }
    7. int GetMindIndex(int* arr, int left, int right)
    8. {
    9. 	int mid = (right + left) / 2;
    10. 	if (arr[left] < arr[mid])
    11. 	{
    12. 		if (arr[mid] < arr[right])
    13. 			return mid;
    14. 		else if (arr[right]
    15. 			return left;
    16. 		else
    17. 			return right;
    18. 	}
    19. 	else
    20. 	{
    21. 		if (arr[mid] > arr[right])
    22. 			return mid;
    23. 		else if (arr[right] > arr[left])
    24. 			return left;
    25. 		else
    26. 			return right;
    27. 	}
    28. }
    29. int PartSort(int* arr, int left, int right)
    30. {
    31. 	int mid = GetMindIndex(arr, left, right);
    32. 	Swap(&arr[mid], &arr[left]);
    33. 	int keyi = left;
    34. 	while (left < right)
    35. 	{
    36. 		while (left < right && arr[right] >= arr[keyi])//left
    37. 		{
    38. 			right--;
    39. 		}
    40. 		while (left < right && arr[left] <= arr[keyi])
    41. 		{
    42. 			left++;
    43. 		}
    44. 		
    45. 		if (left
    46. 			Swap(&arr[left], &arr[right]);
    47. 	}
    48. 	int meeti = left;
    49. 	Swap(&arr[meeti], &arr[keyi]);
    50. 	return meeti;
    51. }
    52. void InsertSort(int* a, int n)
    53. {
    54.  
    55. 		for (int i = 0; i < n -1; i++)
    56. 		{
    57. 			int end = i;
    58. 			int tmp = a[end +1];
    59. 			while (end >= 0)
    60. 			{
    61. 				if (a[end] > tmp)
    62. 				{
    63. 					a[end +1] = a[end];
    64. 					end --;
    65. 				}
    66. 				else
    67. 				{
    68. 					break;
    69. 				}
    70. 			}
    71. 			a[end +1] = tmp;
    72. 		}
    73. }
    74. void QuickSort(int* a, int begin, int end)
    75. {
    76. 	if (begin >= end)
    77. 	{
    78. 		return;
    79. 	}
    80. 	if (end - begin <= 8)
    81. 	{
    82. 		InsertSort(a + begin, end - begin + 1); //a+begin是让从左边开始，每次递归都会导致左边不一样
    83. 	}
    84. 	else
    85. 	{
    86. 		int keyi = PartSort(a, begin, end);
    87. 		QuickSort(a, begin, keyi - 1);//
    88. 		QuickSort(a, keyi + 1, end);
    89. 	}
    90.  
    91. }
    92. int main()
    93. {
    94. 	int arr[] = { 9,1,2,5,7,4,8,6,3,5 };
    95. 	int n = sizeof(arr) / sizeof(arr[0]);
    96. 	QuickSort(arr, 0, n - 1);
    97. 	return 0;
    98. }

    我们可看到这种写法有所优化 

     挖坑法

    1. 先创建一个变量将坑位的值保留，建立俩个指针，分别指向最左边和最右边，若左边为坑，则右指针先走，反之，左指针先走

    2.当右指针遇到比key小的数字，停下来，并把该数字放到hole所指位置 （即填到坑里），自己形成新的坑位

     

    3.然后让左边走，遇到比key大的停下来，把数字填到坑里，然后自己相乘新坑位

    1. void InsertSort(int* a, int n)
    2. {
    3.  
    4. 		for (int i = 0; i < n -1; i++)
    5. 		{
    6. 			int end = i;
    7. 			int tmp = a[end +1];
    8. 			while (end >= 0)
    9. 			{
    10. 				if (a[end] > tmp)
    11. 				{
    12. 					a[end +1] = a[end];
    13. 					end --;
    14. 				}
    15. 				else
    16. 				{
    17. 					break;
    18. 				}
    19. 			}
    20. 			a[end +1] = tmp;
    21. 		}
    22. }
    23. void QuickSort(int* a, int begin, int end)
    24. {
    25. 	if (begin >= end)
    26. 	{
    27. 		return;
    28. 	}
    29. 	if (end - begin <= 8)
    30. 	{
    31. 		InsertSort(a + begin, end - begin + 1);
    32. 	}
    33. 	else
    34. 	{
    35. 		int keyi = PartSort2(a, begin, end);
    36. 		QuickSort(a, begin, keyi - 1);//
    37. 		QuickSort(a, keyi + 1, end);
    38. 	}
    39.  
    40. }
    41. //挖坑法
    42. int PartSort2(int* arr, int left, int right)
    43. {
    44. 	int mid = GetMindIndex(arr, left, right);
    45. 	Swap(&arr[mid], &arr[left]);
    46. 	int hole = left;
    47. 	int key = arr[left];
    48. 	while (left < right)
    49. 	{
    50. 		while (left < right && arr[right] >= key)
    51. 		{
    52. 			right--;
    53. 		}
    54. 		arr[hole]=arr[right];
    55. 		hole = right;
    56. 		while (left < right && arr[left]<= key)
    57. 		{
    58. 			left++;
    59. 		}
    60. 		arr[hole] = arr[left];
    61. 		hole = left;
    62. 	}
    63. 	arr[hole] = key;
    64. 	return hole;
    65. }

     性能跟之前的差不多

     前后指针法

    1.设置俩个指针和一个key，key用来保存数据，俩个指针一前一后，prev在后，cur在前

    2.cur先走，prev接着走，当prev的后一个数字比key大时（也就是cur遇到比key大的数字），prev停下来，cur，继续走，cur遇到比key小的值停下来

    3.停下来之后，prev向前走一步，交换俩数字，之后按照这种方法继续走就行，当cur走到数组之外时，停止，prev会在小于key的位置停下

    1. int PartSort3(int* arr, int left, int right)
    2. {
    3. 	int mid = GetMindIndex(arr, left, right);
    4. 	Swap(&arr[mid], &arr[left]);
    5. 	int keyi = left;
    6. 	int cur = left + 1;
    7. 	int prev = left;
    8. 	while (cur <= right)
    9. 	{
    10. 		if (arr[cur] < arr[keyi] && ++prev != cur)//等于可以不用动那个值，让他留在哪里
    11. 		{
    12. 			Swap(&arr[cur], &arr[prev]);
    13. 		}
    14. 		++cur;
    15. 	}
    16. 	Swap(&arr[keyi], &arr[prev]);
    17. 	return prev;
    18. }
    19. int main()
    20. {
    21. 	int arr[] = { 9,1,2,5,7,4,8,6,3,5 };
    22. 	int n = sizeof(arr) / sizeof(arr[0]);
    23. 	QuickSort(arr, 0, n - 1);
    24. 	return 0;
    25. }

     非递归

    使用递归方式进行快排时，若递归层数较多，则会造成栈溢出，我们可以用数据结构的“栈”来用非递归实现 

    先把起点和终点的下标放进去，这样相当于把第一行的，然后用left和right变量来接收这俩个值，并把这俩个值出栈left=0,right=9

     出栈后，进行排序，并返回他们中间数据的下标，由于我们递归的时候是先递归左边，再递归右边，所以用栈实现的时候也是先对左边排序，再对右边排序，但由于栈是先入后出，所以要先把右边压栈，再把左边压栈，这样出去的时候就是左先出，先计算左，然后右出，再计算右，压栈的时候左和右要和程序里面的left和right相对应

     我们这里在设计的时候是先给右赋值，后给左赋值，再结合我们先给左半边排序再给右半边排序的规则，我们先压5，再压9，之后先压0，再压3

    当中间值下标+1>=右边或者左边+1>=中间值下标的时候我们不需要压栈

    比如这里最后一行最左边0 中间值下标 0 最右边 0，如果进行压栈待会出栈会出来2个0，而数组里面只有一个0，会影响程序的正确性

    1. int PartSort3(int* arr, int left, int right)
    2. {
    3. 	int mid = GetMindIndex(arr, left, right);
    4. 	Swap(&arr[mid], &arr[left]);
    5. 	int keyi = left;
    6. 	int cur = left + 1;
    7. 	int prev = left;
    8. 	while (cur <= right)
    9. 	{
    10. 		if (arr[cur] < arr[keyi] && ++prev != cur)//等于可以不用动那个值，让他留在哪里
    11. 		{
    12. 			Swap(&arr[cur], &arr[prev]);
    13. 		}
    14. 		++cur;
    15. 	}
    16. 	Swap(&arr[keyi], &arr[prev]);
    17. 	return prev;
    18. }
    19. void QuickSort(int* a, int begin, int end)
    20. {
    21. 	if (begin >= end)
    22. 	{
    23. 		return;
    24. 	}
    25. 	if (end - begin <= 8)
    26. 	{
    27. 		InsertSort(a + begin, end - begin + 1);
    28. 	}
    29. 	else
    30. 	{
    31. 		int keyi = PartSort3(a, begin, end);
    32. 		QuickSort(a, begin, keyi - 1);//
    33. 		QuickSort(a, keyi + 1, end);
    34. 	}
    35.  
    36. }
    37.  
    38. void QuickSortNonR(int* a, int begin, int end)
    39. {
    40. 	ST st;
    41. 	StackInit(&st);
    42. 	StackPush(&st, begin);
    43. 	StackPush(&st, end);
    44.  
    45. 	while (!StackEmpty(&st))
    46. 	{
    47. 		int right = StackTop(&st);
    48. 		StackPop(&st);
    49.  
    50. 		int left = StackTop(&st);
    51. 		StackPop(&st);
    52. 		int keyi = PartSort3(a, left, right);
    53. 		// [left, keyi-1] keyi [keyi+1,right]
    54.  
    55. 		if (keyi + 1 < right)//限制条件
    56. 		{
    57. 			StackPush(&st, keyi + 1);
    58. 			StackPush(&st, right);
    59. 		}
    60.  
    61. 		if (left < right - 1) //限制条件
    62. 		{
    63. 			StackPush(&st, left);
    64. 			StackPush(&st, keyi - 1);
    65. 		}
    66. 	}
    67.  
    68. 	StackDestory(&st);
    69. }
    70.  
    71.  
    72. int main()
    73. {
    74. 	int arr[] = {1,2,3,4,5,6,7,8,9,10 };
    75. 	int n = sizeof(arr) / sizeof(arr[0]);
    76. 	QuickSortNonR(arr, 0, n - 1);
    77. 	return 0;
    78. }

  • 相关阅读:
    docker学习进阶篇
    LeetCode·每日一题·1582.二进制矩阵中的特殊位置·模拟
    【面试：并发篇29：多线程：volatile】原理
    SelfKG代码阅读及相关工作
    Python-Flask快速上手
    @Scheduled定时器
    软件测试 -- 进阶 5 软件测试用例
    MyEclipse 用tomcat部署SSM项目后，项目名称和当前项目不一致
    NT68661-屏参升级-RK3128-开机自己升级屏参
    动手学深度学习：2.线性回归pytorch实现
  • 原文地址：https://blog.csdn.net/weixin_49449676/article/details/126340371