# Sort

Here are some tools for sort.

• RandomUtil.java
public class RandomUtil {
public static int[] randomArray(final int size) {
int[] array = new int[size];

Random random = new Random();
for(int i = 0; i < size; i++) {
array[i] = random.nextInt(100);
}

return array;
}
}

• SortUtil.java
public class SortUtil {
private SortUtil(){}

/**
* swap array[index] & array[index+1]
* @param array
* @param index
*/
private static void swap(int[] array, int index) {
int temp = array[index];
array[index] = array[index+1];
array[index+1] = temp;
}

/**
* swap array[dest] & array[target]
* @param array
* @param destIndex
* @param targetIndex
*/
private static void swap(int[] array, int destIndex, int targetIndex) {
int temp = array[destIndex];
array[destIndex] = array[targetIndex];
array[targetIndex] = temp;
}

public static void show(int[] array) {
for(int value : array) {
System.out.print(value+"\t");
}
System.out.println();
}
}


# Bubble sort

TODO优化：

bubble sort

Starting from the beginning of the list, compare every adjacent pair, swap their position if they are not in the right order (the latter one is smaller than the former one). After each iteration, one less element (the last one) is needed to be compared until there are no more elements left to be compared.

• bubbleSort()
public static void bubbleSort(int[] array) {
for(int i = 0; i < array.length-1; i++) {
for(int j = 0; j < array.length-1-i; j++) {
if(array[j] > array[j+1]) {
SortUtil.swap(array, j);
}
}
}
}

• test
@Test
public void testSort() {
int[] array = RandomUtil.randomArray(10);
SortUtil.show(array);

SortUtil.bubbleSort(array);

SortUtil.show(array);
}

• result
39	97	71	51	39	54	13	7	90	39
7	13	39	39	39	51	54	71	90	97

Process finished with exit code 0


We can add a flag to improve the speed of bubble sort, it works well when array has sorted.

• bubbleSortFlag()
public static void bubbleSortFlag(int[] array) {
boolean flag = true;

for(int i = 0; i < array.length-1; i++) {
flag = false;
for(int j = 0; j < array.length-1-i; j++) {
if(array[j] > array[j+1]) {
SortUtil.swap(array, j);

flag = true;
}
}

if(!flag) {
break;
}
}
}


# Selection sort

selection sort

• selectionSort()
public static void selectionSort(int[] array) {
for(int i = 0; i < array.length-1; i++) {
int minIndex = i;
for(int j = i+1; j < array.length; j++) {
if(array[j] < array[minIndex]) {
minIndex = j;    //获取最小下标
}
}

if(minIndex != i) {
swap(array, minIndex, i);
}
}
}

• test
@Test
public void testSelectionSort() {
int[] array = RandomUtil.randomArray(10);
SortUtil.show(array);

SortUtil.selectionSort(array);
SortUtil.show(array);
}

• result
7	19	38	23	63	11	0	55	77	78
0	7	11	19	23	38	55	63	77	78

Process finished with exit code 0


# insertion sort

## 算法描述

1. 从第一个元素开始，该元素可以认为已经被排序

2. 取出下一个元素，在已经排序的元素序列中从后向前扫描

3. 如果该元素（已排序）大于新元素，将该元素移到下一位置

4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

5. 将新元素插入到该位置后

## 实例代码

• 实现 1
public void insertionSort(int[] array) {
for (int i = 1; i < array.length; i++) {
int key = array[i];
int j = i - 1;
while (j >= 0 && array[j] > key) {
array[j + 1] = array[j];
j--;
}
array[j + 1] = key;
}
}

• 实现 2
//将arr[i] 插入到arr[0]...arr[i - 1]中
public static void insertion_sort(int[] arr) {
for (int i = 1; i < arr.length; i++ ) {
int temp = arr[i];
int j = i - 1;
//如果将赋值放到下一行的for循环内, 会导致在第10行出现j未声明的错误
for (; j >= 0 && arr[j] > temp; j-- ) {
arr[j + 1] = arr[j];
}
arr[j + 1] = temp;
}
}