快速排序 订阅
快速排序(Quicksort)是对冒泡排序的一种改进。 [1]  快速排序由C. A. R. Hoare在1960年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。 [1] 展开全文
快速排序(Quicksort)是对冒泡排序的一种改进。 [1]  快速排序由C. A. R. Hoare在1960年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。 [1]
信息
提出时间
1960年
别    称
快速排序
提出者
C. A. R. Hoare
应用学科
计算机科学
中文名
快速排序算法
适用领域范围
Pascal,c++等语言
外文名
quick sort
快速排序算法排序流程
快速排序算法通过多次比较和交换来实现排序,其排序流程如下: [2]  (1)首先设定一个分界值,通过该分界值将数组分成左右两部分。 [2]  (2)将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边。此时,左边部分中各元素都小于或等于分界值,而右边部分中各元素都大于或等于分界值。 [2]  (3)然后,左边和右边的数据可以独立排序。对于左侧的数组数据,又可以取一个分界值,将该部分数据分成左右两部分,同样在左边放置较小值,右边放置较大值。右侧的数组数据也可以做类似处理。 [2]  (4)重复上述过程,可以看出,这是一个递归定义。通过递归将左侧部分排好序后,再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后,整个数组的排序也就完成了。 [2] 
收起全文
精华内容
下载资源
问答
  • 快速排序
    万次阅读 多人点赞
    2019-07-01 17:27:49

    假设对以下10个数进行快速排序:

    61279345108

    我们先模拟快速排序的过程:首先,在这个序列中随便找一个数作为基准数,通常为了方便,以第一个数作为基准数。

    61279345108

    在初始状态下,数字6在序列的第1位。我们的目标是将6挪到序列中间的某个位置,假设这个位置是 k k k。现在就需要寻找这个 k k k,并且以第k位为分界点,左边的数都 ≤ 6 \le6 6,右边的数都 ≥ 6 \ge6 6。那么如何找到这个位置 k k k呢?

    我们要知道,快速排序其实是冒泡排序的一种改进,冒泡排序每次对相邻的两个数进行比较,这显然是一种比较浪费时间的。

    而快速排序是分别从两端开始”探测”的,先从右往左找一个小于6的数,再从左往右找一个大于6的数,然后交换他们。这里可以用两个变量 i i i j j j,分别指向序列最左边和最右边。我们为这两个变量起个好听的名字“哨兵 i i i”和“哨兵 j j j”。刚开始的时候让哨兵 i i i指向序列的最左边,指向数字6。让哨兵 j j j指向序列的最右边,指向数字8。

    61279345108
    ij

    首先哨兵 j j j开始出动。因为此处设置的基准数是最左边的数,所以需要让哨兵 j j j先出动,这一点非常重要。哨兵 j j j一步一步地向左挪动(即 j = j − 1 j = j-1 j=j1),直到找到一个小于6的数停下来。接下来哨兵 i i i再一步一步向右挪动(即 i = i + 1 i=i+1 i=i+1),直到找到一个数大于6的数停下来。最后哨兵 j j j停在了数字5面前,哨兵 i i i停在了数字7面前。

    61279345108
    ij
    现在交换哨兵$i$和哨兵$j$所指向的元素的值。交换之后的序列如下。
    61259347108
    ij

    到此,第一次交换结束。接下来开始哨兵 j j j继续向左挪动(再友情提醒,每次必须是哨兵j先出发)。他发现了 4 < 6 4<6 4<6,停下来。哨兵 i i i也继续向右挪动的,他发现了 9 > 6 9>6 9>6,停下来。此时再次进行交换,交换之后的序列如下。

    61254397108
    ij

    第二次交换结束。哨兵 j j j继续向左挪动,他发现了 3 < 6 3<6 3<6,又停下来。哨兵 i i i继续向右移动,此时哨兵 i i i和哨兵 j j j相遇了,哨兵 i i i和哨兵 j j j都走到3面前。说明此时“探测”结束。我们将基准数6和3进行交换。交换之后的序列如下。

    31254697108
    i,j

    到此第一轮“探测”真正结束。现在基准数6已经归位,此时以基准数6为分界点,6左边的数都小于等于6,6右边的数都大于等于6。回顾一下刚才的过程,其实哨兵 j j j的使命就是要找小于基准数的数,而哨兵 i i i的使命就是要找大于基准数的数,直到 i i i j j j碰头为止。

    现在我们将第一轮“探测"结束后的序列,以6为分界点拆分成两个序列,左边的序列是“3 1 2 5 4”,右边的序列是“9 7 10 8”。接下来还需要分别处理这两个序列。因为6左边和右边的序列目前都还是很混乱的。不过不要紧,我们已经掌握了方法,接下来只要模拟刚才的方法分别处理6左边和右边的序列即可。现在先来处理6左边的序列现吧。

    312546    

    重复第一轮的过程,应该得到如下序列:

    213546    

    OK,现在3已经归位。接下来需要处理3左边的序列:

    213  6    

    处理之后,2已经归位,序列“1”只有一个数,也不需要进行任何处理,因此“1”也归位。

    123  6    

    对于基数右边的序列,采用和左边相同的过程;最终将会得到这样的序列,如下。

    12345678910

    细心的同学可能已经发现,快速排序的每一轮处理其实就是将这一轮的基准数归位,直到所有的数都归位为止,排序就结束了。接下来用图示的方法来展示完整的过程:
    在这里插入图片描述
    快速排序之所以比较快,是因为与冒泡排序相比,每次的交换时跳跃式的,每次排序的时候设置一个基准点,将小于等于基准点的数全部放到基准点的左边,将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换,交换的距离就大的多了。因此总的比较和交换次数就少了,速度自然就提高了。当然在最坏的情况下,仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是 O ( n 2 ) O(n^2) O(n2),它的平均时间复杂度为 O ( n log ⁡ 2 n ) O(n\log_2n) O(nlog2n)

    实现快速排序的代码如下:

    void Quick_Sort(int *arr, int begin, int end){
        if(begin > end)
            return;
        int tmp = arr[begin];
        int i = begin;
        int j = end;
        while(i != j){
            while(arr[j] >= tmp && j > i)
                j--;
            while(arr[i] <= tmp && j > i)
                i++;
            if(j > i){
                int t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
            }
        }
        arr[begin] = arr[i];
        arr[i] = tmp;
        Quick_Sort(arr, begin, i-1);
        Quick_Sort(arr, i+1, end);
    }
    
    更多相关内容
  • 插入排序2.希尔排序 1. 插入排序 步骤: 1.从第一个元素开始,该元素可以认为已经被排序 2.取下一个元素tem,从已排序的元素序列从后往前扫描 3.如果该元素大于tem,则将该元素移到下一位 4.重复步骤3,直到找到已...


    1. 插入排序

    步骤:

    1.从第一个元素开始,该元素可以认为已经被排序
    2.取下一个元素tem,从已排序的元素序列从后往前扫描
    3.如果该元素大于tem,则将该元素移到下一位
    4.重复步骤3,直到找到已排序元素中小于等于tem的元素
    5.tem插入到该元素的后面,如果已排序所有元素都大于tem,则将tem插入到下标为0的位置
    6.重复步骤2~5

    动图演示如下:在这里插入图片描述
    思路:
      在待排序的元素中,假设前n-1个元素已有序,现将第n个元素插入到前面已经排好的序列中,使得前n个元素有序。按照此法对所有元素进行插入,直到整个序列有序。
      但我们并不能确定待排元素中究竟哪一部分是有序的,所以我们一开始只能认为第一个元素是有序的,依次将其后面的元素插入到这个有序序列中来,直到整个序列有序为止。
    在这里插入图片描述
    代码如下:

    void InsertSort(int* arr, int n)
    {
    	for (int i = 0; i < n - 1; ++i)
    	{
    		//记录有序序列最后一个元素的下标
    		int end = i;
    		//待插入的元素
    		int tem = arr[end + 1];
    		//单趟排
    		while (end >= 0)
    		{
    			//比插入的数大就向后移
    			if (tem < arr[end])
    			{
    				arr[end + 1] = arr[end];
    				end--;
    			}
    			//比插入的数小,跳出循环
    			else
    			{
    				break;
    			}
    		}
    		//tem放到比插入的数小的数的后面
    		arr[end  + 1] = tem;
    		//代码执行到此位置有两种情况:
    		//1.待插入元素找到应插入位置(break跳出循环到此)
    		//2.待插入元素比当前有序序列中的所有元素都小(while循环结束后到此)
    	}
    }
    

    时间复杂度:最坏情况下为O(N*N),此时待排序列为逆序,或者说接近逆序
          最好情况下为O(N),此时待排序列为升序,或者说接近升序。
    空间复杂度:O(1)

    2.希尔排序

    步骤:
    1.先选定一个小于N的整数gap作为第一增量,然后将所有距离为gap的元素分在同一组,并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量,重复上述操作…
    2.当增量的大小减到1时,就相当于整个序列被分到一组,进行一次直接插入排序,排序完成。
    动图如下:
    在这里插入图片描述
    思路:
    希尔排序,先将待排序列进行预排序,使待排序列接近有序,然后再对该序列进行一次插入排序,此时插入排序的时间复杂度为O(N),

    代码如下:

    //希尔排序
    void ShellSort(int* arr, int n)
    {
    	int gap = n;
    	while (gap>1)
    	{
    		//每次对gap折半操作
    		gap = gap / 2;
    		//单趟排序
    		for (int i = 0; i < n - gap; ++i)
    		{
    			int end = i;
    			int tem = arr[end + gap];
    			while (end >= 0)
    			{
    				if (tem < arr[end])
    				{
    					arr[end + gap] = arr[end];
    					end -= gap;
    				}
    				else
    				{
    					break;
    				}
    			}
    			arr[end + gap] = tem;
    		}
    	}
    }
    

    时间复杂度平均:O(N^1.3)
    空间复杂度:O(1)

    3.选择排序

    思路:
    每次从待排序列中选出一个最小值,然后放在序列的起始位置,直到全部待排数据排完即可。
    实际上,我们可以一趟选出两个值,一个最大值一个最小值,然后将其放在序列开头和末尾,这样可以使选择排序的效率快一倍。

    动图如下:
    在这里插入图片描述
    代码如下:

    //选择排序
    void swap(int* a, int* b)
    {
    	int tem = *a;
    	*a = *b;
    	*b = tem;
    }
    void SelectSort(int* arr, int n)
    {
    	//保存参与单趟排序的第一个数和最后一个数的下标
    	int begin = 0, end = n - 1;
    	while (begin < end)
    	{
    		//保存最大值的下标
    		int maxi = begin;
    		//保存最小值的下标
    		int mini = begin;
    		//找出最大值和最小值的下标
    		for (int i = begin; i <= end; ++i)
    		{
    			if (arr[i] < arr[mini])
    			{
    				mini = i;
    			}
    			if (arr[i] > arr[maxi])
    			{
    				maxi = i;
    			}
    		}
    		//最小值放在序列开头
    		swap(&arr[mini], &arr[begin]);
    		//防止最大的数在begin位置被换走
    		if (begin == maxi)
    		{
    			maxi = mini;
    		}
    		//最大值放在序列结尾
    		swap(&arr[maxi], &arr[end]);
    		++begin;
    		--end;
    	}
    }
    

    时间复杂度:最坏情况:O(N^2)
          最好情况:O(N^2)
    空间复杂度:O(1)

    4.冒泡排序

    思路:
    左边大于右边交换一趟排下来最大的在右边

    动图如下:
    在这里插入图片描述
    代码如下:

    //冒泡排序
    void BubbleSort(int* arr, int n)
    {
    	int end = n;
    	while (end)
    	{
    		int flag = 0;
    		for (int i = 1; i < end; ++i)
    		{
    			if (arr[i - 1] > arr[i])
    			{
    				int tem = arr[i];
    				arr[i] = arr[i - 1];
    				arr[i - 1] = tem;
    				flag = 1;
    			}
    		}
    		if (flag == 0)
    		{
    			break;
    		}
    		--end;
    	}
    }
    

    时间复杂度:最坏情况:O(N^2)
          最好情况:O(N)
    空间复杂度:O(1)

    5.堆排序

    堆排可看之间这篇博文----->[堆排]

    6.快速排序

    5.1 hoare版本(左右指针法)

    思路:
    1、选出一个key,一般是最左边或是最右边的。
    2、定义一个begin和一个end,begin从左向右走,end从右向左走。(需要注意的是:若选择最左边的数据作为key,则需要end先走;若选择最右边的数据作为key,则需要bengin先走)。
    3、在走的过程中,若end遇到小于key的数,则停下,begin开始走,直到begin遇到一个大于key的数时,将begin和right的内容交换,end再次开始走,如此进行下去,直到begin和end最终相遇,此时将相遇点的内容与key交换即可。(选取最左边的值作为key)
    4.此时key的左边都是小于key的数,key的右边都是大于key的数
    5.将key的左序列和右序列再次进行这种单趟排序,如此反复操作下去,直到左右序列只有一个数据,或是左右序列不存在时,便停止操作,此时此部分已有序

    单趟动图如下:
    在这里插入图片描述
    代码如下:

    //快速排序   hoare版本(左右指针法)
    void QuickSort(int* arr, int begin, int end)
    {
    	//只有一个数或区间不存在
    	if (begin >= end)
    		return;
    	int left = begin;
    	int right = end;
    	//选左边为key
    	int keyi = begin;
    	while (begin < end)
    	{
    		//右边选小   等号防止和key值相等    防止顺序begin和end越界
    		while (arr[end] >= arr[keyi] && begin < end)
    		{
    			--end;
    		}
    		//左边选大
    		while (arr[begin] <= arr[keyi] && begin < end)
    		{
    			++begin;
    		}
    		//小的换到右边,大的换到左边
    		swap(&arr[begin], &arr[end]);
    	}
    	swap(&arr[keyi], &arr[end]);
    	keyi = end;
    	//[left,keyi-1]keyi[keyi+1,right]
    	QuickSort(arr, left, keyi - 1);
    	QuickSort(arr,keyi + 1,right);
    }
    

    时间复杂度:
    在这里插入图片描述
    快速排序的过程类似于二叉树其高度为logN,每层约有N个数,如下图所示:在这里插入图片描述

    5.2 挖坑法

    5.2.1 递归

    思路:
    挖坑法思路与hoare版本(左右指针法)思路类似
    1.选出一个数据(一般是最左边或是最右边的)存放在key变量中,在该数据位置形成一个坑
    2、还是定义一个L和一个R,L从左向右走,R从右向左走。(若在最左边挖坑,则需要R先走;若在最右边挖坑,则需要L先走)

    后面的思路与hoare版本(左右指针法)思路类似在此处就不说了

    单趟动图如下:
    在这里插入图片描述
    代码如下:

    //快速排序法  挖坑法
    void QuickSort1(int* arr, int begin, int end)
    {
    	if (begin >= end)
    		return;
    	int left = begin,right = end;
    	int key = arr[begin];
    	while (begin < end)
    	{
    		//找小
    		while (arr[end] >= key && begin < end)
    		{
    			--end;
    		}
    		//小的放到左边的坑里
    		arr[begin] = arr[end];
    		//找大
    		while (arr[begin] <= key && begin < end)
    		{
    			++begin;
    		}
    		//大的放到右边的坑里
    		arr[end] = arr[begin];
    	}
    	arr[begin] = key;
    	int keyi = begin;
    	//[left,keyi-1]keyi[keyi+1,right]
    	QuickSort1(arr, left, keyi - 1);
    	QuickSort1(arr, keyi + 1, right);
    }
    

    5.2.2 非递归

    //单趟排
    int PartSort(int* arr, int begin, int end)
    {
    	int key = arr[begin];
    	while (begin < end)
    	{
    		while (key <= arr[end] && begin < end)
    		{
    			--end;
    		}
    		arr[begin] = arr[end];
    		while (key >= arr[begin] && begin < end)
    		{
    			++begin;
    		}
    		arr[end] = arr[begin];
    	}
    	arr[begin] = key;
    	int meeti = begin;
    	return meeti;
    }
    
    void QuickSortNoR(int* arr, int begin, int end)
    {
    	stack<int> st;
    	//先入右边
    	st.push(end);
    	//再入左边
    	st.push(begin);
    	while (!st.empty())
    	{
    		//左区间
    		int left = st.top();
    		st.pop();
    		//右区间
    		int right = st.top();
    		st.pop();
    		//中间数
    		int mid = PartSort(arr, left, right);
    		//当左区间>=mid-1则证明左区间已经排好序了
    		if (left < mid - 1)
    		{
    			st.push(mid - 1);
    			st.push(left);
    		}
    		//当mid+1>=右区间则证明右区间已经排好序
    		if (right > mid + 1)
    		{
    			st.push(right);
    			st.push(mid + 1);
    		}
    	}
    }
    

    5.3 前后指针法

    思路:
    1、选出一个key,一般是最左边或是最右边的。
    2、起始时,prev指针指向序列开头,cur指针指向prev+1。
    3、若cur指向的内容小于key,则prev先向后移动一位,然后交换prev和cur指针指向的内容,然后cur指针++;若cur指向的内容大于key,则cur指针直接++。如此进行下去,直到cur到达end位置,此时将key和++prev指针指向的内容交换即可。

    经过一次单趟排序,最终也能使得key左边的数据全部都小于key,key右边的数据全部都大于key。

    然后也还是将key的左序列和右序列再次进行这种单趟排序,如此反复操作下去,直到左右序列只有一个数据,或是左右序列不存在时,便停止操作

    //快速排序法  前后指针版本
    void QuickSort2(int* arr, int begin, int end)
    {
    	if (begin >= end)
    		return;
    	int cur = begin, prev = begin - 1;
    	int keyi = end;
    	while (cur != keyi)
    	{
    		if (arr[cur] < arr[keyi] && ++prev != cur)
    		{
    			swap(&arr[cur], &arr[prev]);
    		}
    		++cur;
    	}
    	swap(&arr[++prev],&arr[keyi]);
    	keyi = prev;
    	//[begin,keyi -1]keyi[keyi+1,end]
    	QuickSort2(arr, begin, keyi - 1);
    	QuickSort2(arr, keyi + 1, end);
    
    }
    
    展开全文
  • 快速排序

    万次阅读 2021-04-15 17:47:44
    它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个...
    • 算法思想
      它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
    • 实现思路
      1、首先设定一个分界值,通过该分界值将数组分成左右两部分。
      2、将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边。此时,左边部分中各元素都小于或等于分界值,而右边部分中各元素都大于或等于分界值。
      3、然后,左边和右边的数据可以独立排序。对于左侧的数组数据,又可以取一个分界值,将该部分数据分成左右两部分,同样在左边放置较小值,右边放置较大值。右侧的数组数据也可以做类似处理。
      4、重复上述过程,可以看出,这是一个递归定义。通过递归将左侧部分排好序后,再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后,整个数组的排序也就完成了。

    转载内容(很生动形象)
    分别从初始序列“6 1 2 7 9 3 4 5 10 8”两端开始“探测”。先从右往左找一个小于6的数,再从左往右找一个大于6的数,然后交换他们。这里可以用两个变量i和j,分别指向序列最左边和最右边。我们为这两个变量起个好听的名字“哨兵i”和“哨兵j”。刚开始的时候让哨兵i指向序列的最左边(即i=1),指向数字6。让哨兵j指向序列的最右边(即=10),指向数字。

    首先哨兵j开始出动。因为此处设置的基准数是最左边的数,所以需要让哨兵j先出动,这一点非常重要。哨兵j一步一步地向左挪动(即j–),直到找到一个小于6的数停下来。接下来哨兵i再一步一步向右挪动(即i++),直到找到一个数大于6的数停下来。最后哨兵j停在了数字5面前,哨兵i停在了数字7面前。


    现在交换哨兵i和哨兵j所指向的元素的值。交换之后的序列如下:

    6 1 2 5 9 3 4 7 10 8


    到此,第一次交换结束。接下来开始哨兵j继续向左挪动(再友情提醒,每次必须是哨兵j先出发)。他发现了4(比基准数6要小,满足要求)之后停了下来。哨兵i也继续向右挪动的,他发现了9(比基准数6要大,满足要求)之后停了下来。此时再次进行交换,交换之后的序列如下:

    6 1 2 5 4 3 9 7 10 8

    第二次交换结束,“探测”继续。哨兵j继续向左挪动,他发现了3(比基准数6要小,满足要求)之后又停了下来。哨兵i继续向右移动,糟啦!此时哨兵i和哨兵j相遇了,哨兵i和哨兵j都走到3面前。说明此时“探测”结束。我们将基准数6和3进行交换。交换之后的序列如下:

    3 1 2 5 4 6 9 7 10 8

    到此第一轮“探测”真正结束。此时以基准数6为分界点,6左边的数都小于等于6,6右边的数都大于等于6。回顾一下刚才的过程,其实哨兵j的使命就是要找小于基准数的数,而哨兵i的使命就是要找大于基准数的数,直到i和j碰头为止。

    OK,解释完毕。现在基准数6已经归位,它正好处在序列的第6位。此时我们已经将原来的序列,以6为分界点拆分成了两个序列,左边的序列是“3 1 2 5 4”,右边的序列是“9 7 10 8”。接下来还需要分别处理这两个序列(递归思想)。因为6左边和右边的序列目前都还是很混乱的。不过不要紧,我们已经掌握了方法,接下来只要模拟刚才的方法分别处理6左边和右边的序列即可。现在先来处理6左边的序列现吧。

    左边的序列是“3 1 2 5 4”。请将这个序列以3为基准数进行调整,使得3左边的数都小于等于3,3右边的数都大于等于3。好了开始动笔吧

    如果你模拟的没有错,调整完毕之后的序列的顺序应该是:

    2 1 3 5 4

    OK,现在3已经归位。接下来需要处理3左边的序列“2 1”和右边的序列“5 4”。对序列“2 1”以2为基准数进行调整,处理完毕之后的序列为“1 2”,到此2已经归位。序列“1”只有一个数,也不需要进行任何处理。至此我们对序列“2 1”已全部处理完毕,得到序列是“1 2”。序列“5 4”的处理也仿照此方法,最后得到的序列如下:

    1 2 3 4 5 6 9 7 10 8

    对于序列“9 7 10 8”也模拟刚才的过程,直到不可拆分出新的子序列为止。最终将会得到这样的序列,如下

    1 2 3 4 5 6 7 8 9 10

    到此,排序完全结束。细心的同学可能已经发现,快速排序的每一轮处理其实就是将这一轮的基准数归位,直到所有的数都归位为止,排序就结束了。下面上个霸气的图来描述下整个算法的处理过程。

    快速排序之所比较快,因为相比冒泡排序,每次交换是跳跃式的。每次排序的时候设置一个基准点,将小于等于基准点的数全部放到基准点的左边,将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换,交换的距离就大的多了。代码如下:

    public static void qsort(int[] arr, int start, int end){
        int pvot = start;
        int left = start;
        int right = end;
    
        if (arr == null || arr.length < 2) {
            return;
        }
    
        if(left > right){
            return;
        }
    
        while(left < right){
    
            //先看右边,依次往左递减
            while( (left < right) && (arr[right] >= arr[pvot]) ){
                right--;
            }
    
            //再看左边,依次往右递增
            while( (left < right) && (arr[left] <= arr[pvot]) ) {
                left++;
            }
    
            System.out.println("left="+left+",right="+right);
            if(left < right){
                int tmp = arr[right];
                arr[right] = arr[left];
                arr[left] = tmp;
            }else{
                //最后将基准为与i和j相等位置的数字交换 也可以放在while 外面执行
                int tmp = arr[right];
                arr[right] = arr[pvot];
                arr[pvot] = tmp;
            }
        }
    
        //递归调用左半数组
        qsort(arr,start,left-1);
        //递归调用右半数组
        qsort(arr,right+1,end);
    }
    
    int[] arr = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8};
    qsort(arr,0 ,arr.length-1);
    for (int i : arr) {
        System.out.print(i + " ");
    }
    
    输出:
    left=3,right=7
    left=4,right=6
    left=5,right=5
    left=2,right=2
    left=1,right=1
    left=4,right=4
    left=8,right=9
    left=8,right=8
    left=7,right=7
    1 2 3 4 5 6 7 8 9 10 

    如果是逆序数组,比如[9 8 7 6 5 4 3 2 1],选取第一个元素作为基准点,那么第一次循环,左游标要执行到最右边,而右游标执行一次,然后两者进行交换。这也会划分成很多的子数组。

    解决方案:三数取中法

    public class QuickSort {
     
        public static void main(String[] args) {
            int[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
            quickSort(arr, 0, arr.length - 1);
            System.out.println("排序结果:" + Arrays.toString(arr));
        }
        
        /**
         * @param arr
         * @param left  左指针
         * @param right 右指针
         */
        public static void quickSort(int[] arr, int left, int right) {
            if (left < right) {
                // 获取枢纽值,并将其放在当前待处理序列末尾
                dealPivot(arr, left, right);
                // 枢纽值被放在序列末尾
                int pivot = right - 1;
                int i = left; // 左指针
                int j = right - 1; // 右指针
                while (true) {
                    while (arr[++i] < arr[pivot]) {
                    }
                    while (j > left && arr[--j] > arr[pivot]) {
                    }
                    if (i < j) {
                        swap(arr, i, j);
                    } else {
                        break;
                    }
                }
                if (i < right) {
                    swap(arr, i, right - 1);
                }
                quickSort(arr, left, i - 1);
                quickSort(arr, i + 1, right);
            }
        }
     
        /**
         * 处理枢纽值
         *
         * @param arr
         * @param left
         * @param right
         */
        public static void dealPivot(int[] arr, int left, int right) {
            int mid = (left + right) / 2;
            if (arr[left] > arr[mid]) {
                swap(arr, left, mid);
            }
            if (arr[left] > arr[right]) {
                swap(arr, left, right);
            }
            if (arr[right] < arr[mid]) {
                swap(arr, right, mid);
            }
            swap(arr, right - 1, mid);
        }
     
        /**
         * 交换元素通用处理
         *
         * @param arr
         * @param a
         * @param b
         */
        private static void swap(int[] arr, int a, int b) {
            int temp = arr[a];
            arr[a] = arr[b];
            arr[b] = temp;
        }
    }
    
    展开全文
  • 快速排序(过程图解)

    万次阅读 多人点赞 2018-07-02 12:10:50
    假设我们现在对“612 79345 108”这个10个数进行排序。首先在这个序列中随便找一个数作为基准数(不要被这个名词吓到了,就是一个用来参照的数,待会你就知道它用来做啥的了)。为了方便,就让第一个数6作为基准数吧...
    假设我们现在对“6  1  2 7  9  3  4  5 10  8”这个10个数进行排序。首先在这个序列中随便找一个数作为基准数(不要被这个名词吓到了,就是一个用来参照的数,待会你就知道它用来做啥的了)。为了方便,就让第一个数6作为基准数吧。接下来,需要将这个序列中所有比基准数大的数放在6的右边,比基准数小的数放在6的左边,类似下面这种排列。
           3  1  2 5  4  6  9 7  10  8
     
            在初始状态下,数字6在序列的第1位。我们的目标是将6挪到序列中间的某个位置,假设这个位置是k。现在就需要寻找这个k,并且以第k位为分界点,左边的数都小于等于6,右边的数都大于等于6。想一想,你有办法可以做到这点吗?
     
            给你一个提示吧。请回忆一下冒泡排序,是如何通过“交换”,一步步让每个数归位的。此时你也可以通过“交换”的方法来达到目的。具体是如何一步步交换呢?怎样交换才既方便又节省时间呢?先别急着往下看,拿出笔来,在纸上画画看。我高中时第一次学习冒泡排序算法的时候,就觉得冒泡排序很浪费时间,每次都只能对相邻的两个数进行比较,这显然太不合理了。于是我就想了一个办法,后来才知道原来这就是“快速排序”,请允许我小小的自恋一下(^o^)。
     
           方法其实很简单:分别从初始序列“6  1  2 7  9  3  4  5 10  8”两端开始“探测”。先从右往左找一个小于6的数,再从左往右找一个大于6的数,然后交换他们。这里可以用两个变量i和j,分别指向序列最左边和最右边。我们为这两个变量起个好听的名字“哨兵i”和“哨兵j”。刚开始的时候让哨兵i指向序列的最左边(即i=1),指向数字6。让哨兵j指向序列的最右边(即j=10),指向数字8。

     
           首先哨兵j开始出动。因为此处设置的基准数是最左边的数,所以需要让哨兵j先出动,这一点非常重要(请自己想一想为什么)。哨兵j一步一步地向左挪动(即j--),直到找到一个小于6的数停下来。接下来哨兵i再一步一步向右挪动(即i++),直到找到一个数大于6的数停下来。最后哨兵j停在了数字5面前,哨兵i停在了数字7面前。

     

     
     
     

           现在交换哨兵i和哨兵j所指向的元素的值。交换之后的序列如下。

            6  1  2  5  9 3  4  7  10  8

     
     
     
            到此,第一次交换结束。接下来开始哨兵j继续向左挪动(再友情提醒,每次必须是哨兵j先出发)。他发现了4(比基准数6要小,满足要求)之后停了下来。哨兵i也继续向右挪动的,他发现了9(比基准数6要大,满足要求)之后停了下来。此时再次进行交换,交换之后的序列如下。
            6  1  2 5  4  3  9  7 10  8
     
            第二次交换结束,“探测”继续。哨兵j继续向左挪动,他发现了3(比基准数6要小,满足要求)之后又停了下来。哨兵i继续向右移动,糟啦!此时哨兵i和哨兵j相遇了,哨兵i和哨兵j都走到3面前。说明此时“探测”结束。我们将基准数6和3进行交换。交换之后的序列如下。
            3  1 2  5  4  6  9 7  10  8
     
     

     
     
            到此第一轮“探测”真正结束。此时以基准数6为分界点,6左边的数都小于等于6,6右边的数都大于等于6。回顾一下刚才的过程,其实哨兵j的使命就是要找小于基准数的数,而哨兵i的使命就是要找大于基准数的数,直到i和j碰头为止。
     
            OK,解释完毕。现在基准数6已经归位,它正好处在序列的第6位。此时我们已经将原来的序列,以6为分界点拆分成了两个序列,左边的序列是“3  1 2  5  4”,右边的序列是“9  7  10  8”。接下来还需要分别处理这两个序列。因为6左边和右边的序列目前都还是很混乱的。不过不要紧,我们已经掌握了方法,接下来只要模拟刚才的方法分别处理6左边和右边的序列即可。现在先来处理6左边的序列现吧。
     
            左边的序列是“3  1  2 5  4”。请将这个序列以3为基准数进行调整,使得3左边的数都小于等于3,3右边的数都大于等于3。好了开始动笔吧。
     
            如果你模拟的没有错,调整完毕之后的序列的顺序应该是。
            2  1  3  5  4
     
            OK,现在3已经归位。接下来需要处理3左边的序列“2 1”和右边的序列“5 4”。对序列“2 1”以2为基准数进行调整,处理完毕之后的序列为“1 2”,到此2已经归位。序列“1”只有一个数,也不需要进行任何处理。至此我们对序列“2 1”已全部处理完毕,得到序列是“1 2”。序列“5 4”的处理也仿照此方法,最后得到的序列如下。
            1  2  3 4  5  6 9  7  10  8
     
            对于序列“9  7  10  8”也模拟刚才的过程,直到不可拆分出新的子序列为止。最终将会得到这样的序列,如下。
            1  2  3 4  5  6  7  8 9  10
     
            到此,排序完全结束。细心的同学可能已经发现,快速排序的每一轮处理其实就是将这一轮的基准数归位,直到所有的数都归位为止,排序就结束了。下面上个霸气的图来描述下整个算法的处理过程。

     
     
            快速排序之所比较快,因为相比冒泡排序,每次交换是跳跃式的。每次排序的时候设置一个基准点,将小于等于基准点的数全部放到基准点的左边,将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换,交换的距离就大的多了。因此总的比较和交换次数就少了,速度自然就提高了。当然在最坏的情况下,仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是O(N2),它的平均时间复杂度为O(NlogN)。
    #include <stdio.h>
    int a[101],n;//定义全局变量,这两个变量需要在子函数中使用
    void quicksort(int left, int right) {
    	int i, j, t, temp;
    	if(left > right)
    		return;
        temp = a[left]; //temp中存的就是基准数
        i = left;
        j = right;
        while(i != j) { //顺序很重要,要先从右边开始找
        	while(a[j] >= temp && i < j)
        		j--;
        	while(a[i] <= temp && i < j)//再找右边的
        		i++;       
        	if(i < j)//交换两个数在数组中的位置
        	{
        		t = a[i];
        		a[i] = a[j];
        		a[j] = t;
        	}
        }
        //最终将基准数归位
        a[left] = a[i];
        a[i] = temp;
        quicksort(left, i-1);//继续处理左边的,这里是一个递归的过程
        quicksort(i+1, right);//继续处理右边的 ,这里是一个递归的过程
    }
    int main() {
    	int i;
        //读入数据
    	scanf("%d", &n);
    	for(i = 1; i <= n; i++)
    		scanf("%d", &a[i]);
        quicksort(1, n); //快速排序调用
        //输出排序后的结果
        for(i = 1; i < n; i++)
        	printf("%d ", a[i]);
        printf("%d\n", a[n]);
        return 0;
    }

     

     
    展开全文
  • 快速排序详解

    千次阅读 2021-11-19 14:29:08
    1.什么是快速排序 我们知道排序有很多种,常见的如希尔排序,插入排序,选择排序,堆排序等等,而快速排序也是排序家族中的一员。因为其在大多数情况下有着优秀的综合性能,快速排序的快速也算是实至名归,接下来就...
  • java的快速排序,快排实现
  • 归并排序与快速排序背后的秘密

    千次阅读 2021-11-03 22:30:23
    到处说归并排序采用了分而治之的方法,所以效率比冒泡排序高: 将一个大问题分解成一些小问题,分而治之,各个击破… 但这些诠释基本都缺少了最关键的点,即效率必须随规模非线性增加的场景,分而治之才有意义,...
  • 快速排序及优化方案

    千次阅读 2022-02-20 18:31:36
    文章目录快速排序及其优化方案1. 快速排序的流程2. 快速排序的实现时间复杂度计算3. 快速排序优化随机获取基准值进行优化3.2二路快速排序原理:思想:4. 总结 快速排序及其优化方案 1. 快速排序的流程 首先设定一个...
  • 图解快速排序(C++实现)

    万次阅读 多人点赞 2019-03-05 10:25:18
    参考大话数据结构这本书对快速排序的讲解,本文作一个梳理,并在最后给出快排的C++实现代码。 假设我们现在对“612 79345 108”这个10个数进行排序。首先在这个序列中随便找一个数作为基准数(不要被这个名词吓到...
  • Python实现快速排序

    千次阅读 2021-07-18 15:32:09
    快速排序(Quicksort)是对冒泡排序算法的一种改进。 二、快速排序分析 三、时间复杂度 最优时间复杂度:O(nlogn) 最坏时间复杂度:O(n2) 稳定性:不稳定 四、快速排序演示 五、完整代码 ...
  • 本期主要讲解:栈溢出的主要原因,内存分布的认识,快速排序和归并排序的非递归算法,结合上期,充分带你学习排序,内含有精美的配图和优质的代码风格!
  • 快速排序算法

    千次阅读 多人点赞 2021-01-11 13:37:49
    文章目录一、快速排序概述1.1 什么是快速排序1.2 快速排序过程解析二、快速排序的具体步骤三、快速排序的代码实现 一、快速排序概述 1.1 什么是快速排序 快速排序(Quick Sort)是对冒泡排序的一种改进。它的基本...
  • 简述冒泡排序与快速排序

    千次阅读 2022-04-29 19:30:26
    简述冒泡排序与快速排序
  • 经典排序算法之:快速排序

    千次阅读 2022-01-18 11:18:39
      快速排序可能是应用最广泛的排序算法。快速排序流行的原因是它实现简单、适用于各种不同的输入数据且在一般应用中比其他排序算法都要快很多。此次,我们来学习一下快速排序算法。 一、快速排序算法含义   快速...
  • 数据结构--排序之快速排序

    千次阅读 多人点赞 2022-02-08 20:09:50
    快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法,其基本思想为:任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有...
  • 十大排序算法——快速排序

    千次阅读 多人点赞 2021-11-18 08:59:19
    快速排序是对冒泡排序的一种改进。 快速排序原理 1.首先设定一个分界值,通过该分界值将数组分成左右两部分﹔ 2.将大于或等于分界值的数据放到到数组右边,小于分界值的数据放到数组的左边。此时左边部分中各...
  • Java快速排序

    千次阅读 2022-03-02 16:53:59
    Java快速排序
  • java快速排序

    千次阅读 2022-03-24 10:04:06
    Java算法——java快速排序 文章目录Java算法——java快速排序一、快速排序简介二、代码实现三、测试用例总结 一、快速排序简介 示例数组: int[] arr = {-9, 78, 0, 0, 1, 0, 3, -1, 23, -56, 7} 简介:快速排序,...
  • 快速排序】(C语言实现)

    千次阅读 多人点赞 2022-04-07 09:16:42
    快速排序一. 递归实现1. 快排是什么?2.实现快排的三种方式a.挖坑法b.左右指针法c.前后指针法二.非递归实现 一. 递归实现 1. 快排是什么? 快速排序算法通过多次比较和交换来实现排序,其排序流程如下: (1)首先设定...
  • 快速排序 定义数组的头部为一个基准,首先从基准的右边比较,交换基准数字;然后从基准的右边比较,交换基准数字。 使基准的左右两边分别都是比基准小和比基准大的数字,完成一次排序。 然后从左右两边分别重新定义...
  • 快速排序算法思想及其优化

    千次阅读 2020-06-23 18:17:05
    前言:快速排序算法是一种排序执行效率很高的排序算法,平均时间复杂度为O (nlogn),明显优于其他排序算法。而且各大互联网公司会高频率问到的快速排序,所以有必要好好学习一下。 一、排序算法简介 1、排序算法...
  • 算法 - 快速排序(C#)

    万次阅读 多人点赞 2019-01-29 20:29:11
    分享一个大牛的人工智能教程。零基础!通俗易懂!风趣幽默!希望你也加入到人工智能的队伍中来!... /* * 快速排序(QuickSort)是对冒泡排序的一种... * 然后再按此方法对这两部分数据分别进行快速排序,整个排序...
  • 排序算法之快速排序

    千次阅读 2020-03-09 17:21:01
    快速排序(Quicksort)是对冒泡排序的一种改进,同冒泡排序一样,快速排序也属于交换排序,通过元素之间的比较与交换位置来达到排序的目的,不同的是,冒泡排序在每一趟只把一个元素冒泡到数列的一端,而快速排序在...
  • 排序算法之快速排序的优化

    千次阅读 2021-03-03 16:59:56
    对 10000 个完全倒序的数进行排序并计一下时,可以发现快速排序是非常慢的!因为此时快速排序已经退化成了冒泡排序! 同时如果输入的数组中的数据完全相同,那么普通的快速排序会产生不必要的划分和递归,既浪费时间又...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 604,003
精华内容 241,601
关键字:

快速排序

友情链接: hdrvdp-master.zip