数据结构之快速排序

1 快速排序

快速排序是一种由分治思想而设计的一种排序算法，其时间复杂度最好为O(nlogn)，最差为O(n*n)，所以该方法是一种不稳定的排序算法。

2 双指针法

双指针法是使用两个指针来定位基准值前后两部分的元素，left和right指针。

需要注意：先对right指针进行比较，然后才对left指针进行比较

2.1 Java代码实现升序排序

public class QuickSort { private int[] array; public QuickSort(int[] array) { this.array = array; } public void increaseSort() { doubleRound(0, this.array.length - 1); } private void doubleRound(int start, int end) { if (start >= end) return; int pIndex = swepDoubleRound(start, end); doubleRound(start, pIndex - 1); doubleRound(pIndex + 1, end); } //升序排序 private int swepDoubleRound(int start, int end) { int l = start, r = end; //左右指针，分别指向头和尾 int p = this.array[start]; //基准值，以第一个元素为基准值 while (l != r) { //当左指针小于右指针，且右指针指向的元素大于基准元素时，右指针左移,表示当前元素需要放在数组后半部分 while (l < r && this.array[r] > p) r--; //当左指针小于右指针，且左指针指向的元素小于等于基准元素时，左指针右移，表示当前元素需要放在数组前半部分 while (l < r && this.array[l] <= p) l++; //当左右指针都不在移动时，交换左右指针位置上的值 if (l < r) { int t = this.array[l]; this.array[l] = this.array[r]; this.array[r] = t; } } //当左右指针重合时，次数当前比较结束，并将基准元素和中间元素交换，使用左和右指针都可以 this.array[start] = this.array[l]; this.array[l] = p; return l; } }

2.2 Java代码实现降序排序

public class QuickSort { private int[] array; public QuickSort(int[] array) { this.array = array; } public void decreaseSort(){ doubleRound2(0,this.array.length-1); } //降序排序 private void doubleRound2(int start, int end) { if (start >= end) return; int pIndex = swepDoubleRound2(start, end); doubleRound2(start, pIndex - 1); doubleRound2(pIndex + 1, end); } //降序排序 private int swepDoubleRound2(int start, int end) { int l = start, r = end; //左右指针，分别指向头和尾 int p = this.array[start]; //基准值，以第一个元素为基准值 while (l != r) { //当左指针小于右指针，且右指针指向的元素大于基准元素时，右指针左移,表示当前元素需要放在数组后半部分 while (l < r && this.array[r] < p) r--; //当左指针小于右指针，且左指针指向的元素小于等于基准元素时，左指针右移，表示当前元素需要放在数组前半部分 while (l < r && this.array[l] >= p) l++; //当左右指针都不在移动时，交换左右指针位置上的值 if (l < r) { int t = this.array[l]; this.array[l] = this.array[r]; this.array[r] = t; } } //当左右指针重合时，次数当前比较结束，并将基准元素和中间元素交换，使用左和右指针都可以 this.array[start] = this.array[l]; this.array[l] = p; return l; } }

3 单指针法

3.1 升序排序

public class QuickSort { private int[] array; public QuickSort(int[] array) { this.array = array; } //升序排序 public void increaseSortBySingle() { singleRound(0, this.array.length - 1); } //升序排序 private void singleRound(int start, int end) { if (start >= end) return; int pivotIndex = swepSingleRound(start, end); singleRound(start, pivotIndex - 1); singleRound(pivotIndex + 1, end); } //升序排序 private int swepSingleRound(int start,int end) { int p = this.array[start]; int mark = start; for (int i = start+1; i <= end; i++) { /** * 如果当前元素a[i]小于基准元素的值，那么mark指针右移一位，此时将mark指针上的值和a[i]交换 */ // System.out.println("start="+start+",end="+end+",pivot="+p+",i="+i+","+Arrays.toString(this.array)+",a["+i+"]="+this.array[i]); if (this.array[i] < p){ mark++; int t = this.array[mark]; this.array[mark] = this.array[i]; this.array[i]=t; } } //最后将mark指针上的元素和基准元素交换 this.array[start] = this.array[mark]; this.array[mark] = p; return mark; } }

3.2 降序排序

public class QuickSort { private int[] array; public QuickSort(int[] array) { this.array = array; } //降序排序 public void decreaseSortBySingle() { singleRound2(0, this.array.length - 1); } //降序排序 private void singleRound2(int start, int end) { if (start >= end) return; int pivotIndex = swepSingleRound2(start, end); singleRound2(start, pivotIndex - 1); singleRound2(pivotIndex + 1, end); } //降序排序 private int swepSingleRound2(int start,int end) { int p = this.array[start]; int mark = start; for (int i = start+1; i <= end; i++) { /** * 如果当前元素a[i]大于基准元素的值，那么mark指针右移一位，此时将mark指针上的值和a[i]交换 */ // System.out.println("start="+start+",end="+end+",pivot="+p+",i="+i+","+Arrays.toString(this.array)+",a["+i+"]="+this.array[i]); if (this.array[i] > p){ mark++; int t = this.array[mark]; this.array[mark] = this.array[i]; this.array[i]=t; } } //最后将mark指针上的元素和基准元素交换 this.array[start] = this.array[mark]; this.array[mark] = p; return mark; } }