你的位置:首页 > Java教程

[Java教程]排序—快速排序


快速排序:

  1、从数组中随便选出一个数(其实一般用第一个数)作为本次循环的比较基数,然后走一趟,把所有比基数小的数放在该基数的左边,把大于该基数的数放在该基数的右边(排序结果有小到大,反之反之)。

    (该基数在数组中的脚标是变动的,不要考虑比该基数小(大)的数较多,在其左(右)边放不下的弱智脑残问题)

      2、通过递归来实现,把小于该基数的数(或者大于该基数的数)作为一个新的数组,重复第一步操作。

            不熟练递归的看这里: http://www.cnblogs.com/PerkinsZhu/p/5668218.html

重点来了:怎么通过循环一趟把小于该基数的数移动到其左边,大于该基数的数移动到其右边呢?怎么办呢?这是个问题!!!

               这么干:取第一个数为基数,然后从数组的右边向左边依次取数比较,一直找到比基数小的数(记录该数的index为right),然后交换两数位置,停止从右向左寻找。

          开始从左向右寻找,找到比该基数大的数(记录该数index为left),然后交换两数的位置,停止从左向右寻找。

           开始从右向左寻找……开始从左向右寻找……   明白吗?一直循环,终止条件是:数组中的除基数外所有的数都与该基数比较过,也就是right=left。

运行示例:

 

原数组:     21、8、2、18、0、9、27、12、5、24、
第0次循环排序结果: 5、8、2、18、0、9、27、12、21、24、
第1次循环排序结果: 5、8、2、18、0、9、21、12、27、24、
第2次循环排序结果: 5、8、2、18、0、9、12、21、27、24、
第3次循环排序结果: 0、8、2、18、5、9、12、21、27、24、
第4次循环排序结果: 0、5、2、18、8、9、12、21、27、24、
第5次循环排序结果: 0、2、5、18、8、9、12、21、27、24、
第6次循环排序结果: 0、2、5、12、8、9、18、21、27、24、
第7次循环排序结果: 0、2、5、9、8、12、18、21、27、24、
第8次循环排序结果: 0、2、5、8、9、12、18、21、27、24、
第9次循环排序结果: 0、2、5、8、9、12、18、21、24、27、

 

 

好了,看代码吧:

    

public void callQuickSort(int[] array) {    printArray("原数组:", array);    quickSort(array, 0, array.length - 1);  }  public void quickSort(int[] array, int left, int right) {    if (left >= right)      return;    int index = qSort(array, left, right);    quickSort(array, left, index);    quickSort(array, index + 1, right);  }  private int qSort(int[] array, int left, int right) {    int mid = left;    int temp;    while (left < right) {      if (mid != right) {        if (array[mid] > array[right]) {          temp = array[right];          array[right] = array[mid];          array[mid] = temp;          mid = right;          printArray("第" + time++ + "次循环排序结果: ", array);        } else {          right--;        }      } else {        if (array[left] > array[mid]) {          temp = array[left];          array[left] = array[mid];          array[mid] = temp;          mid = left;          printArray("第" + time++ + "次循环排序结果: ", array);        } else {          left++;        }      }    }    return mid;  }