之前看了一点关于数据结构和算法的文章，这是个充满魅力的领域，想简单总结分享一下
冒泡排序
从小到大：
- 初始化两个指针，分别指向第一个元素（索引0）和第二个元素（索引1）；
- 比较相邻两个元素的大小，若右侧的元素（index+1）小于左侧（index）,则交换位置，否则不变；
- 指针同时右移一个单位；
- 重复第二步，直到到达数组末尾；
- 末尾索引减一（已是最大），重复1，2，3，直到无须交换；
冒泡的特点：每一次轮回后（步骤4），末排序的值都会“冒”到正确的位置，然后继续轮回，继续冒泡；
冒泡实战：
public static int[] bubbleSort(int[] arr) {
// 初始化第一次最终冒泡的位置，及最后一个索引
int lastSortedIndex = arr.length-1;
// 初始化设定为排序
boolean sorted = false;
while (!sorted) {
sorted = true;
for (int i = 0; i < lastSortedIndex; i++) {
if (arr[i] > arr[i + 1]) {
sorted = false;
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
lastSortedIndex--;
}
return arr;
}
public static void main(String[] args) {
int[] arr = {2, 3, 1, 5, 4};
System.out.println(Arrays.toString(bubbleSort(arr))); // 1,2,3,4,5
}
冒泡的效率：
比较：(N-1)+(N-2)+(N-3)+...+1
交换：最坏：(N-1)+(N-2)+(N-3)+...+1，最好：0
时间复杂度：O(N²)
选择排序
从小到大：
- 从左往后，记录最小值的索引，最小值初始为索引0的值，如果当前索引的值小于最小值，则更新最小的索引为当前索引，直到数组的最后一位；
- 将最小值与本次检查的起点交换；
- 初始最小值的索引进一位，重复前两步，直到排序完成（起点索引为最大索引）
选择特点：选择最小值索引。比较时，只记录索引值，不做置位操作，直到本次数组比较完毕，再进行至多一次交换，最小值将依次向后排列
选择实战：
public static int[] selectionSort(int[] arr) {
// 从小到大排序，依次最小的值
for (int i = 0; i < arr.length; i++) {
// 初始化最小值的索引
int minIdenx = i;
for (int j = i+1; j < arr.length; j++) {
// 当前索引值小于当前最小值，更新索引
if (arr[j] < arr[minIdenx]) {
minIdenx = j;
}
}
// 当前最小值的索引不在起点
if (minIdenx != i) {
int temp = arr[i];
arr[i] = arr[minIdenx];
arr[minIdenx] = temp;
}
}
return arr;
}
public static void main(String[] args) {
int[] arr = {2, 3, 1, 5, 4};
System.out.println(Arrays.toString(selectionSort(arr)));
}
选择效率：
比较：(N-1)+(N-2)+(N-3)+...+1
交换：最多：N-1，最少：0（每轮1或0次）
时间复杂度：O(N²/2) ——>忽略常数——>O(N²)
选择排序的步数大概只有冒泡的一半
插入排序
从小到大：
- 移出：第一轮，先将第二个元素（索引1）的值移出，保存到临时变量，并记录当前空隙位置的指针，且当前数组中第二个元素处于空隙状态；
- 比较并平移：临时变量与空隙左侧的值挨个比较，若空隙左侧的值大于临时变量，则该值向右移动一位，空隙自动左移（指针减一），若当前值比临时变量小，或空隙已到达最左则，平移结束；
- 插入：将临时变量填入空隙；
- 重复前三步，直到数组有序
插入特点：每轮四个步骤，移出，比较，平移，插入
插入实战：
public static int[] insertionSort(int[] arr) {
// 从第二个元素开始移出
for (int i = 1; i < arr.length; i++) {
// 初始空隙所在位置的指针
int position = i;
// 当前移出值保存到临时变量
int tempValue = arr[i];
// 直到空隙移到最左侧，或当前值小于临时变量，则将临时变量插入空隙
while (position > 0 && arr[position - 1] > tempValue) {
// 不符合条件，将左侧值右移一位，即：将左侧的值赋给右侧，指针减一
arr[position] = arr[--position];
}
// 临时变量插入当前空隙的指针
arr[position] = tempValue;
}
return arr;
}
public static void main(String[] args) {
int[] arr = {2, 3, 1, 5, 4};
System.out.println(Arrays.toString(insertionSort(arr)));
}
插入效率：
移出：N-1
比较：最多：1+2+3+...+N-1=N²/2，最少：N-1
平移：最多：N²/2，最少：0（有序）
插入：N-1
时间复杂度：O(N²+2N-2)——>简化——>O(N²)，最坏、平均、最好情况：N2、N2/2、N步
快速排序
分区：
- 从数组从随机选取一个值，以其为轴，将比它小的值放在左边，比它大的之放到右边
- 放置两个指针，分别指向除轴元素的数组最左和最又的元素
- 左指针逐个索引向右移动，当遇到大于等于轴的值就停下来；
- 右指针逐个索引向左移动，当遇到小于等于轴的值就停下来；
- 将两个指针所指的值交换位置；
- 重复3，4，5，直到两个指针重合，或左指针移到右指针的右边；
- 将轴与左指针所在的位置交换；
- 当分区完成时，在轴左侧的那些值肯定比轴要小，在轴右侧的那些值肯定比轴要大
从小到大：
- 将数组分区，使轴到正确的位置；
- 对轴左右的两个子数组递归地重复1、2步，也就是说，两个子数组都各自分区，并形成各自的轴以及由轴分隔的更小的子数组。然后也对这些子数组分区，依次类推；
- 当分出的子数组长度为0或1时，即达到基准情形，无需进一步操作
快速特点：一次分区至少有N次比较，及数组的每个值都要与轴做比较；每次分区，左右指针豆花从两端开始靠近，直到相遇
实战：
public class TestQuickSort {
public static int partition(int[] arr, int leftPointer, int rightPointer) {
// 总是取最右的值作为轴
int pivotPosition = rightPointer;
int pivot = arr[pivotPosition];
// 将右指针指向轴左边的一格
rightPointer -= 1;
while (true) {
// 左指针只要小于轴，右移，不能超过轴
while (arr[leftPointer] < pivot && leftPointer < pivotPosition) {
leftPointer += 1;
}
// 右指针只要小于轴，左移
while (arr[rightPointer] > pivot && rightPointer > 0) {
rightPointer -= 1;
}
if (leftPointer >= rightPointer) {
break;
} else {
swap(arr, leftPointer, rightPointer);
}
}
// 将左指针的值与轴交换
swap(arr, leftPointer, pivotPosition);
// 返回左指针
return leftPointer;
}
public static void swap(int[] arr, int pointer1, int pointer2) {
int tempValue = arr[pointer1];
arr[pointer1] = arr[pointer2];
arr[pointer2] = tempValue;
}
public static int[] quickSort(int[] arr, int leftPointer, int rightPointer) {
// 基准情形：分出的子数组长度为0或1
if (rightPointer - leftPointer <= 0) {
return arr;
}
// 将数组分成两部分，并返回分隔所用的轴的索引
int pivotPosition = partition(arr, leftPointer, rightPointer);
// 对轴左侧的部分递归调用quicksort
quickSort(arr, leftPointer, pivotPosition - 1);
// 对轴右侧的部分递归调用quicksort
quickSort(arr, pivotPosition + 1, rightPointer);
return arr;
}
public static void main(String[] args) {
// int[] arr = {0, 5, 2, 1, 6, 4};
int[] arr = {5, 6, 0, 4, 3, 2, 1, 4};
int[] sort = quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(sort));
}
}
快速效率：
比较：每个值都要与轴比较
交换：在适当时候将左右指针所指的两个值交换位置
时间复杂度：一次分区，最少交换1次，最多N/2次，分区——>O(N)；总共——>O(NlogN)
最好：O(NlogN)，平均O(NlogN)，最坏O(N²)（每次分区都是轴落在数组的开头或结尾，如已升序或降序）
参考书籍：数据结构与算法图解-【美】杰伊·温格罗
