189 8069 5689

c语言快速排序实现方法-创新互联

  • 快排
  • 原理：
    • 从待排序区间选择一个数，作为基准值(pivot)
    • Partition: 遍历整个待排序区间，将比基准值小的（可以包含相等的）放到基准值的左边，将比基准值大的（可以包含相等的）放到基准值的右边
    • 采用分治思想，对左右两个小区间按照同样的方式处理，直到小区间的长度等于1，代表已经有序，或者小区间的长度等于0，代表没有数据。
  • 快排是一个不稳定的排序
实现方式

  1. 快排的逻辑其实很简单，

    创新互联公司是一家集网站建设,平桂企业网站建设,平桂品牌网站建设,网站定制,平桂网站建设报价,网络营销,网络优化,平桂网站推广为一体的创新建站企业，帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿，时刻以成就客户成长自我，坚持不断学习、思考、沉淀、净化自己，让我们为更多的企业打造出实用型网站。
    • 递归分治

    • 代码如下：

      public static void quickSort(int[] array) {
     //待排序区间为[0, array.length - 1]
     quickSortIternal(array, 0, array.length - 1);
}

private static void quickSortIternal(int[] array, int left, int right) {
     if(left >= right)
         return;

     //这里的就选择最左边的元素作为基准值来操作
     //index表示基准值停留的下标
     int index = partition(array, left, right);

     quickSortIternal(array, left, index - 1);
     quickSortIternal(array, index + 1, right);
}
    • 非递归分治
    • 通过使用栈实现，将数组的左右下标放入栈中
    • 每次取出判断left和right的关系，如果left >= right 表示该小区间排序完毕
    • 存入每个区间的左右两下标，依次循环，当栈为空时，表示排序结束

    • 代码如下：

      public static void quickSort2(int[] array) {
       Stack stack = new Stack<>();
       stack.push(array.length - 1);
       stack.push(0);

       while(!stack.isEmpty()) {
           int left = stack.pop();
           int right = stack.pop();

           if(left >= right) {
               continue;
           }

           int index = partition(array, left, right);

           stack.push(right);
           stack.push(index + 1);

           stack.push(index - 1);
           stack.push(left);
       }
   }

  2. 重点是partition的实现

    • 实现方法一： Hoare法
    • 使用双引用的的方式，一个指向区间的最左边，一个指向区间的最右边，两个引用向中间遍历的靠拢
    • 如果左引用指向的值小于等于基准值就移动
    • 如果右引用指向的值大于等于基准值就移动
    • 当左引用遇到大于基准值的数据且右引用遇到小于基准值的数据时，交换这两个引用处的数据
    • 当两个引用相遇时说明本次partition结束，返回基准值的下标

    • 代码如下：

      public int partition(int[] array, int left, int right) {
       int pivot = array[left];
       int l = left;
       int r = right;

       while(l < r) {
           while(l < r && array[r] >= pivot) {
               r--;
           }
           while(l < r && array[l] <= pivot) {
               l++;
           }
           swap(array, l, r);
       }
       swap(array, left, l);
       return l;
   }

   private static void swap(int[] array, int i, int j) {
       int tmp = array[i];
       array[i] = array[j];
       array[j] = tmp;
   }
    • 实现方法二：填坑法
    • 同样需要双引用，指定一个变量保存基准值，假象基准值的位置是一个“坑”
    • 右引用遇到大于等于基准值的数值就向左移动，直到遇到第一个小于基准值的数值，将该数值填到“坑”中，此处的位置是一个新的“坑”
    • 开始移动左引用，只有遇到一个大于基准值的数值时，填到“坑”中
    • 直到左引用和右引用相遇时说明只剩最后一个坑了，将基准值填到“坑”中，返回基准值的下标，本次partition结束

    • 代码如下：

      public int partition(int[] array, int left, int right) {
   int pivot = array[left];
   int l = left;
   int r = right;

   while(l < r) {
       while(l < r && array[r] >= pivot) {
           r--;
       }
       array[l] = array[r];
       while(l < r && array[l] <= pivot) {
           l++;
       }
       array[r] = array[l];
   }
   array[l] = pivot;
   return l;
}
    • 实现方法三：前后遍历法
    • 同样是使用双引用slow和fast，起初同时指向基准值的后一个元素left + 1
    • 引用fast向后遍历，如果遍历到的数值大于基准值就向后移动
    • 遇到小于基准值的数值时，交换slow引用和fast引用指向的值，slow向后移动一位
    • 始终保证slow之前的值都是小于基准值的数值，slow和fast之间的是大于等于基准值的数值，当fast移动到区间最右端right时，遍历结束
    • 此时show - 1处的数值为最遍历结束后最后一个小于基准值的数值
    • 交换left和slow - 1两位置处的数值，slow - 1表示下标即是基准值的下标，返回slow - 1

    • 代码如下：

      private int partition(int[] array, int left, int right) {
       int pivot = array[left];
       int slow = left + 1;
       int fast = left + 1;

       while(fast <= right) {
           if(array[fast] < pivot) {
               swap(array, slow, fast);
               slow++;
           }
           fast++;
       }
       swap(array, left, slow - 1);
       return slow - 1;
   }
  3. 基准值的选择
    • 两边取其一（左或者右）
    • 随机选择
    • 几数取中（例三数取中：array[left], array[mid], array[right] 大小是中间的为基准值 ）
性能分析
  • 时间复杂度：
    • 最好的情况：O(N*logN)
    • 平均情况：O(N*logN)
    • 最坏的情况：O(N^2)
  • 空间复杂度：O(1)
    • 最好的情况：O(logN)
    • 平均情况：O(logN)
    • 最坏的情况：O(N)
  • 稳定性：不稳定

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。


网页标题：c语言快速排序实现方法-创新互联
文章URL：http://cdxtjz.cn/article/dcghpo.html

其他资讯