快速排序左右交换法 partition函数输出基准下标

忘是亡心i 2022-12-15 02:26 99阅读 0赞

#include <stdio.h>
    #include <stdlib.h>
    int partition(int *p,int left,int right)
    { 
     int temp=p[left];//基准 
     int i=left,j=right; 
     int k;
     while(i<j)
     {   while(i<j&&p[j]>=temp)j--;//寻找比基准数小的数 
        while(i<j&&p[i]<=temp)i++;//寻找比基准数大的数 
        if(i<j)
        { k=p[i];p[i]=p[j];p[j]=k;
        //交换 两个数 小的在左边 大的在右边 
        }
     }
      int t;//交换基准数下标 和i所指的数据 
      t=p[left];p[left]=p[i];p[i]=t;  
      
        }
    void quicksort(int *p,int left,int right)
    { if(left<right)
     { int pos=partition(p,left,right);
      quicksort(p,left,pos-1);
      quicksort(p,pos+1,right);
                   } 
         }
    int main(int argc, char *argv[])
    { 
      int m;
      scanf("%d",&m);
      int a[m];
      for(int i=0;i<m;i++)
      scanf("%d",&a[i]);
      quicksort(a,0,m-1);
      for(int i=0;i<m;i++)
      printf("%d",a[i]);
      system("PAUSE");	
      return 0;
    }

![在这里插入图片描述][20201014183156883.png_pic_center]

左右交换法  
加上递归的应用

[20201014183156883.png_pic_center]: /images/20221123/002cdd381bf54e969824c521c19a9219.png

发表评论取消回复

表情：

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

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

相关阅读

相关交换排序之快速排序

快速排序的核心思想： 1. 每一轮选取一个随机的数字作为参照，一般选取本轮的第一个数字，然后设置两个指针，分别指向序列头部和尾部； 2. 与参照数字作比较，左边遇到大

逃离我推掉我的手/ 2023年07月18日 02:49/ 0 赞/ 8 阅读

相关快速排序左右交换法 partition函数输出基准下标

include <stdio.h> include <stdlib.h> int partition(int p,int left,int right)

忘是亡心i/ 2022年12月15日 02:26/ 0 赞/ 100 阅读

相关交换排序(冒泡排序、快速排序)

1、冒泡排序 1.1、概念冒泡排序是通过对排序序列从前向后(从下标较小的元素开始)、依次比较相邻元素的值，若发现逆序则交换，使较大的元素逐渐从前移向后部，就像水底

雨点打透心脏的1/2处/ 2022年11月27日 15:45/ 0 赞/ 203 阅读

相关交换排序：快速排序

快速排序（Quicksort）是对冒泡排序算法的一种改进。快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成

分手后的思念是犯贱/ 2022年10月16日 02:59/ 0 赞/ 178 阅读

相关快速排序算法里的partition函数

快速排序算法里的partition函数用来解决这样一个问题：给定一个数组arr\[\]和数组中任意一个元素a，重排数组使得a左边都小于它，右边都不小于它。 ![复制代码][c

Dear 丶/ 2022年07月16日 00:43/ 0 赞/ 124 阅读

相关排序（四）之快速排序指针交换法

在上一节讲的填坑法基础上，再修改一下，指针交换法的原理是，也是先移动右指针，找到一个符合条件的元素，再移动左指针，找到一个符合条件的元素，，右指针找到的是比基准元素小的，左指针

阳光穿透心脏的1/2处/ 2022年05月13日 08:50/ 0 赞/ 155 阅读

相关交换类排序-----快速排序

//快速排序 include<stdio.h>//时间复杂度 O(nlogn) 不稳定 void QuickSort(int a[], int n

水深无声/ 2022年05月03日 01:56/ 0 赞/ 165 阅读

相关交换法排序

include<stdio.h> include<stdlib.h> / 插入排序法 / / written by Chen Gengru /

客官°小女子只卖身不卖艺/ 2022年04月21日 15:40/ 0 赞/ 149 阅读

相关交换排序——快速排序

/ 算法思想：在待排序元素中选定一个作为中间数，使该数据表中的其他元素的关键字与“中间数” 的关键字相比较，将整个数据表划分成为

电玩女神/ 2022年03月20日 02:54/ 0 赞/ 211 阅读

相关排序 - 交换排序 [2 -- 快速排序]

“傻文，如果你也跟我一样没有耐性，看我的文章吧，专为没有耐性的朋友准备” 研究了几天这个快速排序的算法，可能我比较笨，断断续续加起来估计超过5个小时的时间

雨点打透心脏的1/2处/ 2022年01月12日 15:59/ 0 赞/ 224 阅读