package com.learn.sort;
/**
* 基本排序--选择排序 冒泡排序 插入排序 希尔排序
*
* 下面所有的排序默认为升序
*/
public class BaseSort {
/**
* 选择排序 选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的
* 数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。 选择排序比冒泡排序时间上要优秀一点，
* 主要在于，冒泡排序每次比较都需要交换位置，而选择排序通过记录最大或最小位置的索引最后只交换一次位置就可以了
*
* @param arr
*/
public static void selectSort(Comparable[] arr) {
int n = arr.length;
for (int i = 0; i < n; i++) {
// 寻找[i,n)区间里的最小值的索引
int minIndex = i;
for (int j = i + 1; j < n; j++)
// 使用compareTo方法比较两个Comparable对象的大小
if (arr[j].compareTo(arr[minIndex]) < 0)
minIndex = j;
swap(arr, i, minIndex);
}
}
/**
* 冒泡排序 冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。
* 它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。
* 走访数列的工作是重复地进行直到没有再需要交换，
* 也就是说该数列已经排序完成。
* @param arr
*/
public static void bubbleSort(Comparable[] arr) {
int n = arr.length;
for (int i = n - 1; i >= 0; i--) {
for (int j = 1; j <= i; j++)
if (arr[j - 1].compareTo(arr[j]) > 0)
swap(arr, j - 1, j);
}
}
/**
* 优化后的冒泡排序
*
* @param arr
*/
public static void bubbleSort2(Comparable[] arr) {
int n = arr.length;
int newn;// 使用newn进行优化
do {
newn = 0;
for (int i = 1; i < n; i++) {
if (arr[i - 1].compareTo(arr[i]) > 0) {
swap(arr, i - 1, i);
// 记录最后一次的交换位置，在此之后的元素在下一轮扫描中均不考虑
newn = i;
}
}
n = newn;
} while (newn > 0);
}
/**
* 插入排序 有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，
* 这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，
* 从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。
* 插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置）
* ，而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。
* 插入排序的基本思想是：每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
*
* @param arr
*/
public static void insertSort(Comparable[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
Comparable temp = arr[i];
int j = i;
for (; j > 0 && temp.compareTo(arr[j - 1]) < 0; j--)
arr[j] = arr[j - 1];
arr[j] = temp;
}
}
/**
* 希尔排序 希尔排序的实质就是分组插入排序，该方法又称缩小增量排序，因DL．Shell于1959年提出而得名
* 该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）
* 分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，
* 再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），
* 效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高
*
* @param arr
*/
public static void shellSort(Comparable[] arr) {
int n = arr.length;
int h = 1;
while (h < n / 3)
h = 3 * h + 1;
while (h >= 1) {
for (int i = h; i < n; i++) {
Comparable e = arr[i];
int j = i;
for (; j >= h && e.compareTo(arr[j - h]) < 0; j -= h)
arr[j] = arr[j - h];
arr[j] = e;
}
h /= 3;
}
}
private static void swap(Object[] arr, int i, int j) {
Object t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
public static void main(String[] args) {
// 测试Integer
Integer[] a = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
BaseSort.bubbleSort2(a);
for (int i = 0; i < a.length; i++) {
System.out.print(a[i]);
System.out.print(' ');
}
System.out.println();
// 测试Double
Double[] b = { 4.4, 3.3, 2.2, 1.1 };
BaseSort.selectSort(b);
for (int i = 0; i < b.length; i++) {
System.out.print(b[i]);
System.out.print(' ');
}
System.out.println();
// 测试String
String[] c = { "D", "C", "B", "A" };
BaseSort.selectSort(c);
for (int i = 0; i < c.length; i++) {
System.out.print(c[i]);
System.out.print(' ');
}
System.out.println();
}
}