Java教程

排序算法-快速排序

本文主要是介绍排序算法-快速排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

1、快速排序

快速排序(Quicksort)是对冒泡排序算法的一种改进。

算法思路

快速排序算法的排序流程如下:

  • 1.先从数列中取出一个数作为基准数。
  • 2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。
  • 3.再对左右区间重复第二步,直到各区间只有一个数。  

 

一趟快速排序的算法是:

1)设置两个变量i、j,排序开始的时候:i=0,j=N-1;

2)以第一个数组元素作为基准数,赋值给pivot,即pivot=A[0]=A[i];

3)由后向前搜索(j--),找到第一个小于pivot的值A[j],将A[j]和A[i]的值交换;

4)由前向后搜索(i++),找到第一个大于pivot的A[i],将A[i]和A[j]的值交换;

5)重复第3、4步,直到i==j;

 

 

经过第1趟排序,数组被划分为两个区,5左边是小于5的{2,3,0,1,4},Flag右边是大于Flag的{6,7,9,10,8}。我们再分别对这两个区进行递归操作,直至每个组里只剩下1个数字,排序完成!

代码

package com.hsp.baselearn.algorithm;

import java.util.Arrays;

/**
 * 快速排序
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = { 5, 3, 7, 6, 4, 1, 0, 2, 9, 10, 8 };
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));

    }

    private static void quickSort(int[] arr,int low,int hige) {
     if(low<hige){
         // 1. 定义基准pivot,
         int pivot = arr[low];
         // ...... pivot移动到中间,左边都比pivot小,后边都比pivot大, index
         int i= low;
         int j= hige;

         while (i<j){
             //移动右边
             while (i<j && arr[j]>=pivot){
                 j--;
             }
             //交换位置
             swap(arr,i,j);

             //移动左边元素
             while (i<j && arr[i]<=pivot){
                 i++;
             }
             //交换位置
             swap(arr,i,j);


         }

         //此时j=1 递归对左右2部分快排
         quickSort(arr,low,j-1);
         quickSort(arr,j+1,hige);
     }
    }

    private static void swap(int[] arr,int i,int j){
        int temp  = arr [i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
}

 

这篇关于排序算法-快速排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!