快速排序QuickSort

古城微笑少年丶 2022-09-22 11:56 113阅读 0赞

题目：快速排序

//挖坑法
    #include<iostream>
    using namespace std;
    #include<assert.h>
    int Single(int *arr, int left, int right)
    {
    	assert(arr);     
    	int tmp = arr[right];  //tmp作为坑
    	while (left < right)   //
    	{
    		while (left < right&&tmp >= arr[left]) 
    		{//要找左边比tmp大的，所以只要arr[left]比tmp小，指针就后移
    			left++;
    		}
    		if (left < right)//边界条件
    		{//此时tmp和right所指的就是坑，将左边的数据填进去，指针right左移
    			arr[right--] = arr[left];
    		}
    		while (left < right&&tmp <= arr[right])
    		{//此时左边的left所指位置就是坑，查找右边数据比tmp小的，然后填进去
    			right--;
    		}
    		if (left < right)
    		{//将右边的小的数据挪到左边来
    			arr[left++] = arr[right];
    		}
    	}
    	//最后移动完后，left和right相遇,将tmp赋值给随意一个
    	
    	arr[left] = tmp;
    	//arr[right] = tmp;
    	return left;
    }
    
    void QuickSort(int *arr, int left, int right)
    {
    	if (arr == NULL)
    	{
    		return;
    	}
    	if (left < right)
    	{
    		int div = Single(arr, left, right);
    		QuickSort(arr, left, div - 1);
    		QuickSort(arr, div + 1, right);
    	}
    }
    
    int main()
    {
    	int arr[] = { 9, 8, 7, 0, 5, 4, 3, 2, 1, 6 };
    	QuickSort(arr, 0,sizeof(arr) / sizeof(arr[0])-1);
    	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
    	{
    		cout << arr[i] << " ";
    	}
    	system("pause");
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，113人围观）

还没有评论，来说两句吧...

相关阅读

相关快速排序（Quicksort）算法

基本思想通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以

亦凉/ 2024年04月08日 11:54/ 0 赞/ 15 阅读

相关【模板】快速排序与归并排序——Template，QuickSort&MergeSort

快速排序 include<iostream> using namespace std; int n,a[1000001]; void qsor

秒速五厘米/ 2022年11月12日 02:51/ 0 赞/ 150 阅读

相关快速排序QuickSort

题目：快速排序 //挖坑法 include<iostream> using namespace std; include<

古城微笑少年丶/ 2022年09月22日 11:56/ 0 赞/ 114 阅读

相关排序之快速排序java quicksort

不多说直接上代码： package jsoup; import java.util.Arrays; public class Qu

约定不等于承诺〃/ 2022年07月13日 02:20/ 0 赞/ 124 阅读

相关【数据结构】快速(QuickSort)排序之——前后指针法

快速排序的定义：快速排序(Quick Sort)是一种有效的排序[算法][Link 1]。虽然[算法][Link 1]在最坏的情况下运行时间为O(n^2)，但由于平均运行时

ゝ一纸荒年。/ 2022年06月16日 12:40/ 0 赞/ 132 阅读

相关快速排序（Quicksort）学习笔记

看完邓俊辉的《数据结构（第三版）》中快速排序后的学习总结一.快速排序（Quicksort）：基于分治策略的又一经典算法。类似于归并排序（Mergesort）。将序列分为

喜欢ヅ旅行/ 2022年06月01日 05:45/ 0 赞/ 264 阅读

相关用Python实现快速排序(Quicksort)算法

1.快速排序(Quicksort)算法介绍 > 快速排序（Quicksort）是对冒泡排序的一种改进,但是不是稳定的排序算法 2.算法思想 > 1

蔚落/ 2022年05月06日 14:57/ 0 赞/ 553 阅读

相关 Java数组排序：Java快速排序（Quicksort）法

快速排序（Quicksort）是对冒泡排序的一种改进。快速排序的基本思想是：通过一趟排序，将要排序的数据分隔成独立的两部分，其中一部分的所有数据比另外一部分的所有数

阳光穿透心脏的1/2处/ 2021年12月16日 14:43/ 0 赞/ 321 阅读

相关排序算法6：快速排序（QuickSort）

排序算法：快速排序(QuickSort) 快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(

蔚落/ 2021年09月28日 22:18/ 0 赞/ 307 阅读

相关内部排序之快速排序（QuickSort）

一、基本思想快速排序法是对冒泡法的改进。基本思想为：从列表中任选一个记录作为枢纽。然后从列表的开始和结束位置向中间遍历，把记录的关键字与枢纽进行比较。小于枢纽的

待我称王封你为后i/ 2021年09月11日 01:48/ 0 赞/ 314 阅读