选择排序
- 算法步骤
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕。
-
动图演示
image
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class selectionSort {
public static void main(String[] args) {
List<Integer> ls = new ArrayList<Integer>(Arrays.asList(5,4,3,2,1));
selectionSort ss = new selectionSort();
ss.selection(ls);
System.out.println(ls.toString());
}
private static void selection(List<Integer> ls){
int index=0;
int temp;
for (int i=0;i< ls.size()-1;i++){
for (int j=i;j<ls.size();j++){
if (ls.get(i) > ls.get(j)){
index = j;
}
}
temp = ls.get(i);
ls.set(i, ls.get(index));
ls.set(index, temp);
}
}
}
插入排序
- 算法步骤
将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
-
动图演示
image
package sorted;
public class InsertSort{
public static void main(String[] args) {
int[] array = {5,4,3,2,1};
InsertSort is = new InsertSort();
is.insertSort(array);
for (int num:
array) {
System.out.println(num);
}
}
public static void insertSort(int[] array){
int insertVal = 0;
int insertIndex = 0;
for (int i=1;i<array.length;i++) {
insertIndex = i;
insertVal = array[i];
while(insertIndex>0 && insertVal<array[insertIndex-1]){
array[insertIndex] = array[insertIndex-1];//将大的数后移，不插插入值
insertIndex--;
}
array[insertIndex] = insertVal;//最后插入值
}
}
}
希尔排序
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；
希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。
- 算法步骤
选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
按增量序列个数 k，对序列进行 k 趟排序；
每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
-
动图演示
image
image.png
package sorted;
import java.util.Arrays;
public class Shell {
public static void main(String[] args){
int [] array = {5,9,4,7,8,6,0,3,2,1};
Shell shell = new Shell();
shell.shellSort(array);
System.out.println(Arrays.toString(array));
}
public static void shellSort(int [] array){
int len = array.length;
int l = array.length;
int value = 0;
int index = 0;
while(l>=1){
l = (int)l/2;
for (int i=0;i<l;i++){
for(int j = i+l;j<len;j+=l){
value = array[j];
index = j;//希尔改进位移式，交换式效率低
while(index>i && value<array[index-l]){
array[index] = array[index-l];
index = index-l;
}
array[index] = value;
}
}
}
}
}
快速排序（重点）
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。
快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。
快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！它是处理大数据最快的排序算法之一了。虽然 Worst Case 的时间复杂度达到了 O(n²)，但是人家就是优秀，在大多数情况下都比平均时间复杂度为 O(n logn) 的排序算法表现要更好，可是这是为什么呢，我也不知道。好在我的强迫症又犯了，查了 N 多资料终于在《算法艺术与信息学竞赛》上找到了满意的答案：
快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。
- 算法步骤
从数列中挑出一个元素，称为 "基准"（pivot）;
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；
此图为双边循环法，还有单边循环法（复习的时候实现！！！！）
还有非递归实现方式，后续探究，
package sorted;
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
int [] array = {5,9,4,7,8,6,0,3,2,1,-100};
quickSort(array,0, array.length-1);
System.out.println(Arrays.toString(array));
}
public static void quickSort(int []array, int start,int end){
int pivot = array[(start+end)>>1];
int left = start;
int right = end;
int temp = 0;
while(left<right){
while(array[left]<pivot){
left++;
}
while(array[right]>pivot){
right--;
}
if(left>=right){
break;
}
temp = array[right];
array[right] = array[left];
array[left] = temp;
if(array[left] == pivot){
right--;
}
if(array[right] == pivot){
left++;
}
}
if(left==right){
left++;
right--;
}
if(start<right) {
quickSort(array, start, right);
}
if (left<end) {
quickSort(array, left, end);
}
}
}
