首页 > 代码库 > 再次学习快速排序

再次学习快速排序

2024-07-17 12:58:00   220人阅读

 

 

快速排序已经看过好几遍了，经常因为小的bug，写错程序，为了以后少犯类似的错误，在这记下来。

快速排序的原理比较简单，运用递归的思想，每次用一个元素将原来的数组进行分割，关键是找对分割的位置。将前后两部分分割成小于分割元素和大于分割元素，然后递归对前后两部分继续快速排序

两部分代码：

第一部分是快速排序的整体思想:

public static void quicksort(int[] list){         quicksort(list,0,list.length-1);    }    private static void quicksort(int[] list, int low, int high) {        if(low<high){            int index = partition(list,low,high);            quicksort(list,low,index-1);            quicksort(list,index+1,high);        }            }

第二部分是找分割的位置：

经常犯错误的地方：在判断privot与list[low]list[high]时，丢掉“=”的判断，

private static int partition(int[] list, int first, int last) {        int privot = list[low];        int low= first+1;
　　　　　int high = last;        while(low<high){            while(low<=high&&privot>=list[low]){                low++;            }            while(low<=high&&privot<list[high]){                high--;            }            if(low<high){                int temp = list[low];                list[low] = list[high];                list[high] = temp;            }        }        if(privot>list[high]){            list[first] = list[high];            list[high] = privot;            return high;        }else{            return first;        }            }

测试类：

public static void main(String[] args) {        int[] list = {2,3,2,5,6,1,-2,3,14,12};        quicksort(list);        for(int i:list){            System.out.print(i+" ");        }    }

 


联系
我们