Jimmy小站
小明也有大梦想 — 蒋明/铭小明学排序-快速排序
2016-03-23 / 数据结构算法 / 4015 次围观 / 1 次吐槽快速排序法,原则是首先选中一个元素作为参考元。
一般选择首元素或中间元素等。
本代码使用首元素。
令下标 i , j 分别从头尾分别向中间靠拢,直到 i = j 时停止,
将左边大于参考元素的值的元素换到右边,
同理右边按照要求换到左边,完成一层迭代。
接下来以 下标 i (此时 i = j)作为分割点,分成左右两组。
再分别迭代进行快速排序。
package net.jimmyme; import java.util.Arrays; public class QuickSort { public static void main(String[] args) { int[] source = {101,8,9,13,45,17,26,99,78,11,46,999,111}; quickSort(source,0,source.length-1); System.out.println(Arrays.toString(source)); } public static void quickSort(int[] source, int left, int right){ int i = left; int j = right; int key = source[left]; while (i < j) { while (i < j && source[j] >= key) { j--; } if (i < j) { source[i] = source[j]; i++; } // 此时 j 下标的值 < key ,如果下标没有越界,换到左边去(source[i] 保存) // 最开始的source[i]保存在key 中,接下来的source[i]保存在前一轮的source[j]中 // source[j] 保存在前一轮的source[i]中 while (i < j && source[i] <= key) { i++; } if (i < j) { source[j] = source[i]; j--; } } // 此时,i = j source[i] = key; if (left < i && left >=0) { quickSort(source, left, i-1); } if (j < right && j >= 0) { quickSort(source, j+1, right); } } }
- 上一篇:小明学排序-归并排序算法
- 下一篇:冒泡排序,选择排序,插入排序,希尔排序
本月热文
Copyright © Jimmy小站 Allrights Reserved.备案号:桂ICP备 15005996
已有1位网友发表了看法:
发表评论