快速排序原理及Java代码实现

这个本来是我大二应该写的博文，没想到却是因为大四找工作复习才回来写。。

对于初学者的经验就是，按照代码，自己拿一个数组动手操作一遍就能懂了。本来大二死记硬背的东西，现在经过考研过后，原理掌握清楚了，自己现在就可以自然而然的写出来。所以我个人觉得，真正理解原理才是最重要的。

原理：利用递归。每一次递归，我们都会取数组当中的一个数（这个数是随机的，不过大多数教材都喜欢取未排序的数组的第一个数）当作枢纽。在每一次的递归后，这个枢纽都会被放在它最后排序好的位置。它的左边，全都是比它小的数；它的右边，全都是比它大的数。接下来，我们就把该枢纽左边的数当作信新的数组再次进行递归；右边的数，同样当作新的数组进行递归。经过多次递归之后，粒度慢慢变小，最终就可以达到我们想要的结果。

乍一看真的很像归并排序，对吧。

原理清楚了，下面就看代码的实现。

这个函数是用来交换数组的两个数的位置的：
    public static void swap(int[] array,int index1,int index2)
    {
        int temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;
    }

//这个函数为递归的主体
    public static int[] QuickSort(int[] array,int low,int high)
    {
        if(low < high)
        {
            int pivot = Partion(array,low,high);
            //每次经过Partition这个函数，都会又一个数放在正确的位置上，pivot是枢纽的位置
            
            QuickSort(array,low,pivot-1);
           //把枢纽左边的这些数，当成新的数组进行递归

            QuickSort(array,pivot+1,high);
            //把枢纽右边的这些数，当成新的数组进行递归
        }
        return array;
        //此时返回的数组是已经排序好了的数组
    }

//该函数的作用就是把枢纽放到正确的位置上
    public static int Partion(int[] array,int low,int high)
    {
    //这里的low和high我喜欢把它们叫做指针，low目前指向数组最左边的位置，high目前指向数组最右边的位置
    
        int pivot = array[low];
		//取该未排序的数组的第一个数当作枢纽

        while(low < high)
        {
            while(low < high && array[high] > pivot)
                high--;
			//当high指针所指的数大于枢纽的值时，我们认为它满足条件，移动指针的位置即可

            swap(array,low,high);
			//能够到这一步，代表，现在high指针指向的数，是小于枢纽的，不符合规定。我们将low和high指向的两个数进行交换；另一种可能就是所有的数均符合规定，此时low=high


            while(low < high && array[low] < pivot)
                low++;
			//当low指针所指的数小于枢纽的值时，我们认为它满足条件，移动指针的位置即可

    
            swap(array,low,high);
            //能够到这一步，代表，现在low指针指向的数，是枢纽的，不符合规定。我们将low和high指向的两个数进行交换；另一种可能就是所有的数均符合规定，此时low=high
        }

        return low;
        //此处说明，low和high所指向的位置是重合的。它们重合的这个位置，救赎枢纽所在位置。
    }

下面是全部代码的整合，没有注释，仅提供运行

public class Practie
{
    public static void main(String[] arg)
    {
        int[] array = {6,5,4,3,2,1};
        array = QuickSort(array,0,array.length-1);
        for(int i=0;i<array.length;i++)
        {
            System.out.println(array[i]);
        }
    }
    public static void swap(int[] array,int index1,int index2)
    {
        int temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;
    }

    public static int[] QuickSort(int[] array,int low,int high)
    {
        if(low < high)
        {
            int pivot = Partion(array,low,high);
            QuickSort(array,low,pivot-1);
            QuickSort(array,pivot+1,high);
        }
        return array;
    }

    public static int Partion(int[] array,int low,int high)
    {
        int pivot = array[low];
        while(low < high)
        {
            while(low < high && array[high] > pivot)
                high--;
            swap(array,low,high);
            while(low < high && array[low] < pivot)
                low++;
            swap(array,low,high);
        }

        return low;
    }
}

结尾不知道自己想说什么，自己还能说什么。
不管是考研失败还是现在工作还没有下落。每天给自己加油，也其实没什么用。但是不管自己现在如何，只有努力才能继续往下走。自己如果都不相信自己，那就没有人可以相信自己了。