排序算法(Java实现)：选择排序法和快速排序法
为了方便扩展，先引入一个抽象的基础类：
- package com.andyidea.algorithms;
- /**
- * 排序抽象基础类
- * @author Andy.Chen
- *
- * @param <T>
- */
- public abstract class Sorter<T extends Comparable<T>> {
- public abstract void sort(T[] array,int from,int len);
- public final void sort(T[] array){
- sort(array,0,array.length);
- }
- protected final void swap(T[] array,int from,int to){
- T tmp = array[from];
- array[from] = array[to];
- array[to] = tmp;
- }
- }
选择排序算法源码如下：
- package com.andyidea.algorithms;
- /**
- * 选择排序法
- * @author Andy.Chen
- *
- * @param <T>
- */
- public class SelectionSort<T extends Comparable<T>> extends Sorter<T> {
- @Override
- public void sort(T[] array, int from, int len) {
- for(int i=from;i<from+len;i++){
- int smallestindex = i;
- int j = i;
- for(; j<from+len; j++){
- if(array[j].compareTo(array[smallestindex])<0){
- smallestindex = j;
- }
- }
- swap(array, i, smallestindex);
- }
- }
- }
【四】快速排序：快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。
快速排序算法的具体操作描述如下：
- 从数列中挑出一个元素，称为 "基准"（pivot），
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
快速排序算法源码如下：
- package com.andyidea.algorithms;
- /**
- * 快速排序法
- * @author Andy.Chen
- *
- * @param <T>
- */
- public class QuickSort<T extends Comparable<T>> extends Sorter<T> {
- @Override
- public void sort(T[] array, int from, int len) {
- quick_sort(array, from, from+len-1);
- }
- private void quick_sort(T[] array,int from, int to){
- if(to-from < 1)
- return;
- int pivot = selectPivot(array, from, to);
- pivot = partition(array, from, to, pivot);
- quick_sort(array, from, pivot-1);
- quick_sort(array, pivot+1, to);
- }
- /**
- * 选择基准元素
- * @param array
- * @param from
- * @param to
- * @return
- */
- private int selectPivot(T[] array,int from, int to){
- return (from+to)/2;
- }
- /**
- * 分区操作
- * @param array
- * @param from
- * @param to
- * @param pivot
- * @return
- */
- private int partition(T[] array, int from, int to, int pivot){
- T tmp = array[pivot];
- array[pivot] = array[to];
- while(from != to){
- while(from<to && array[from].compareTo(tmp)<=0)
- from++;
- if(from<to){
- array[to] = array[from];
- to--;
- }
- while(from<to && array[to].compareTo(tmp)>=0)
- to--;
- if(from<to){
- array[from] = array[to];
- from++;
- }
- }
- array[from] = tmp;
- return from;
- }
- }
相关推荐
IT之家 2020-03-11
graseed 2020-10-28
zbkyumlei 2020-10-12
SXIAOYI 2020-09-16
jinhao 2020-09-07
impress 2020-08-26
liuqipao 2020-07-07
淡风wisdon大大 2020-06-06
yoohsummer 2020-06-01
chenjia00 2020-05-29
baike 2020-05-19
扭来不叫牛奶 2020-05-08
hxmilyy 2020-05-11
黎豆子 2020-05-07
xiongweiwei00 2020-04-29
Cypress 2020-04-25
冰蝶 2020-04-20