这段时间在复习数据结构与算法,准备花点时间好好捋一捋基础
在日常的项目中，排序算法可以说是程序员的基础了。而且面试中也有较大几率被问到，下面让我们回顾一下几个基础的排序算法。
选择排序
选择排序时间复杂度为O(n^2),大致思想就是每次选择最小的元素将其放在数组的前端，然后不停的迭代就行，由于比较简单，也不多说。简单的看一下演示图，和我的代码实现
SelectionSort.gif
由于大部分排序都要交换数组中元素的位置，所以写一个swap（）函数
private static void swap(Object[] arr, int i, int j) {
Object t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
下面就是排序算法了
public static void sort(Comparable[] arr) {
int len = arr.length;
for (int i = 0; i < len; i ++) {
int minIndex = i;
for (int j = i + 1; j < len; j ++) {
if (arr[j].compareTo(arr[minIndex]))
minIndex = j;
}
swap(arr,i, minIndex);
}
}
插入排序
插入排序时间复杂度同样为O(n^2)，思路与选择排序类似，就是每次与之前一个元素进行比较，如果比前面那个元素小，就插入那个元素前面
InsertionSort.gif
public static void sort(Comparable[] arr){
int len= arr.length;
for (int i = 0; i < len; i++) {
Comparable t= arr[i];
int j = i;
for( ; j > 0 && arr[j-1].compareTo(t) > 0 ; j--)
arr[j] = arr[j-1];
arr[j] = t;
}
}
冒泡排序
冒泡排序可以说是我会的第一个排序算法了，实现起来也很简单，就是将大的元素不断的冒泡，到数组的最后面
BubbleSort.png
public static void sort(Comparable[] arr){
int len = arr.length;
for (int i = len - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
if (arr[j].compareTo(arr[j + 1]) > 0) {
swap(arr, j, j + 1);
}
}
}
}
希尔排序
希尔排序实质上是分组插入排序，先取一定的增量将数组分割成若干个序列进行插入排序，然后再缩小增量进行排序，直到增量为1（PS： 不知道为什么我写的这个希尔排序效率非常低，数据比较多的时候，比其他算法都要慢上不少，过几日我要改进一下）
image.png
public static void sort(Comparable[] arr) {
int len = arr.length;
int d = len / 2;
while (d >= 1) {
for (int i = 0; i < arr.length; i++){
for (int j = i; j < arr.length - d; j += d) {
if (arr[i].compareTo(arr[j + d]) > 0) {
swap(arr, j , j+d);
}
}
}
d = d /2;
}
}
上面都是些比较简单的算法，明后天将为大家带来快速排序和双路快排和三路快排，分析一下快速排序有时效率较低的原因
