- 直接插入排序
- 1、思想：直接插入排序是一种简单的插入排序法，基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。比如玩扑克牌时，整理扑克就用了这个思想。
- 2、实现：当插入第（i>=1）个元素时，前面的array[0],array[1]…array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2]…的排序码顺序进行比较，找到插入位置将array[i]插入，原来位置行的元素顺序后移
- 代码实现：
void InsertSort(int *num, int len)
{
int i, j, temp;
for (i = 1; i < len; i++)
{
// num[i]之前的序列是有序的，num[i - 1]为有序部分的最大值
// 故只需要与有序部分的最大值进行比较，即可判断是否需要插入
if (num[i - 1] > num[i])
{
// 获取需要插入的数据
temp = num[i];
// 依次后移，查找插入位置
for ( j = i - 1; num[j] > temp && j >= 0; j--)
{
num[j + 1] = num[j];
}
// 完成插入
num[j + 1] = temp;
}
}
}
特性：元素集合越接近有序，直接插入排序算法效率的时间效率越高；最好O(N)顺序有序，最坏O(N^2)接近有序；空间复杂度O(1)。
- 希尔排序
- 1、思想：希尔排序法又称缩小增量法。希尔排序法的基本思想是：step1先选定一个整数gap
- 实现
- 代码
- 实现
- 1、思想：希尔排序法又称缩小增量法。希尔排序法的基本思想是：step1先选定一个整数gap
int shsort(int s[], int n)
{
int i,j,d;
d=n/2;
while(d>=1)
{
for(i=d+1;i<=n;i++)
{
s[0]=s[i];
j=i-d;
while((j>0)&&(s[0]
s[j+d]=s[j];
j=j-d;
}
s[j + d]=s[0];
}
d = d/2;
}
return 0;
}
特性:希尔排序是对直接插入排序的优化（先分组，对分组对数据进行插入排序）；当gap>1的时候都是预排序，目的是让数组更接近于有序。当gap==1时，数组已经接近有序了；时间复杂度：O(N^1.3) ~ O(N^2) 空间复杂度 ： O(1)
- 选择排序
- 思想：每一次从待排序列元素中选出最小（或最大）对一个元素，存放在序列的起始（最后）位置，直到全部待排序的数据元素排完。
- 实现：step1在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素；step2若它不是这组元素中的最后一个（第一个）元素，则将它与这组元素中的最后一个（第一个）元素交换；step3在剩余的array[i]–array[n-2] or（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素
- 代码实现
void SelectSort(int* a, int n)
{
int left = 0, right = n - 1;
while (left < right)
{
// 选出最大的值和最小的值
int minIndex = left, maxIndex = left;
for (int i = left; i <= right; ++i)
{
if (a[i] < a[minIndex])
minIndex = i;
if (a[i] > a[maxIndex])
maxIndex = i;
}
Swap(&a[left], &a[minIndex]);
// 如果max和left位置重叠，max被换走了，要修正一下max的位置 !!!
if (left == maxIndex)
{
maxIndex = minIndex;
}
Swap(&a[right], &a[maxIndex]);
++left;
--right;
}
特性：①直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用；②时间复杂度：O(N^2) 空间复杂度 ： O(1)
- 堆排序
- 思想：堆事一种数据结构，一种叫做完全二叉树的数据结构。堆排序是指利用堆这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据，需要注意的是排升序要建大堆，排降序要建小堆。
- 实现：
堆排序的实现有一个重要的算法： 向下调整算法( 用于建大堆 )
① 从根结点处开始，选出左右孩子中值较大的孩子下标。
② 让值较大的孩子与其父亲进行比较。
③ 如果值孩子比父亲大，将父亲的值 和 孩子的值交换 ，并将原来值较大的孩子的位置当成父亲，循环到 ① 继续向下进行调整，直到调整到叶子结点为止。如果值孩子比父亲小，则不需处理了，调整完成，整个树已经是大堆了。
堆排序的前提是有一个堆。
(1) 如何建堆? 利用向下调整算法将原数组调整为一个大堆。
2) 如何进行堆排序呢？
1、将堆顶数据与堆的最后一个数据交换，此时产生一个新的堆，不包含交换到最后位置的那一个数据，然后从堆顶位置进行一次向下调整。
2、经过步骤 1 堆中最大的数据又位于堆顶，循环执行步骤 1 ，每次把堆中的最大数据与堆的最后一个数据进行交换，以此类推就形成了一个有序的序列。
- 代码实现
void AdjustDwon(int* a, int n, int root)
{
int parent = root;
int child = parent * 2 + 1;
while (child < n) //一直向下调整
{
if (child + 1 < n && a[child + 1] > a[child]) //child防止越界 找最大child的下标
{
child++;
}
if (a[parent] < a[child])
{
Swap(&a[parent], &a[child]);
parent = child;
child = parent * 2 + 1;
}
else //没有比parent大的结束
{
break;
}
}
}
void HeapSort(int* a, int n)
{
//刚开始自底向上调整 建堆 - 从倒数第二层开始
for (int i = (n - 1 - 1) / 2; i >= 0; --i)
{
AdjustDwon(a, n, i);
}
int end = n - 1; //依次从堆顶拿到最大值放到后面
while (end > 0)
{
Swap(&a[0], &a[end]);
AdjustDwon(a, end, 0);
--end;
}
}
特性分析：
①堆的向下调整算法的时间复杂度： 最坏的情况下（即一直需要交换结点），需要循环的次数为：h - 1次（h为树的高度）。而h = log2(N + 1) （N为树的总结点数）。所以堆的向下调整算法的时间复杂度为：O(logN) 。
②建堆的时间复杂度 ： 假设高度为k，则从倒数第二层右边的节点开始，这一层的节点都要执行子节点比较然后交换（如果顺序是对的就不用交换）；倒数第三层呢，则会选择其子节点进行比较和交换，如果没交换就可以不用再执行下去了。如果交换了，那么又要选择一支子树进行比较和交换；高层也是这样逐渐递归。
那么总的时间计算为：s = 2^( i - 1 ) * ( k - i )；其中 i 表示第几层，2^( i - 1) 表示该层上有多少个元素，( k - i) 表示子树上要下调比较的次数。
S = 2^(k-2) * 1 + 2(k-3)2……+2(k-2)+2(0)*(k-1) ===> 因为叶子层不用交换，所以i从 k-1 开始到 1；
S = 2^k -k -1；又因为k为完全二叉树的深度，而log(n) =k，把此式带入；
得到：S = n - log(n) -1，所以时间复杂度为：O(n)
③排序重建堆： 在取出堆顶点放到对应位置并把原堆的最后一个节点填充到堆顶点之后，需要对堆进行重建，只需要对堆的顶点调用AdjustDown() 函数。
每次重建意味着有一个节点出堆，所以需要将堆的容量减一。AdjustDown() 函数的时间复杂度k=log(n)，k为堆的层数。所以在每次重建时，随着堆的容量的减小，层数会下降，函数时间复杂度会变化。重建堆一共需要n-1次循环，每次循环的比较次数为log(i)，则相加为：log2+log3+…+log(n-1)+log(n)≈log(n!)。可以证明log(n!)和nlog(n)是同阶函数：
∵(n/2)n/2≤n!≤nn,
∴n/4log(n)=n/2log(n1/2)≤n/2log(n/2)≤log(n!)≤nlog(n)
所以时间复杂度为O(nlogn)
④小结 ： 初始化建堆的时间复杂度为O(n)，排序重建堆的时间复杂度为nlog(n)，所以总的时间复杂度为O(n+nlogn)=O(nlogn)。另外堆排序的比较次数和序列的初始状态有关，但只是在序列初始状态为堆的情况下比较次数显著减少，在序列有序或逆序的情况下比较次数不会发生明显变化。
⑤空间复杂度： O(1)
- 冒泡排序
- 思想：所谓交换，就是根据序列中两个记录健值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将健值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。
- 实现：
- 代码实现
package com.kuang.array;
import java.util.Arrays;
public class ArrayDemo07 {
public static void main(String[] args) {
int[] a = {1,4,5,6,7,8,10};
System.out.println(Arrays.toString(sort(a)));
System.out.println(Arrays.toString(a));
}
//冒泡排序
//1、比较数组中，两个相邻的元素，如果第一个数比第二个数大，我们就交换他们的位置
//2、每一次比较，都会产生一个最大，或者最小的数字；
//3、下一轮则可以少一次排序！
//4、依次循环，直到结束！
public static int[] sort(int[] array){
int temp = 0;
//外层循环，判断我们这个要走多少次；
for (int i = 0;i < array.length-1;i++){
boolean flag = false;//通过flag标识位减少没有意义大比较
//内层循环，比较判断两个数，如果第一个数比第二个数大则交换他两的位置
for (int j=0;j < array.length-1-i;j++){
if (array[j+1]>array[j]){
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
flag = true;
}
}
if (flag == false){
break;
}
}
return array;
}
}
特性总结：
① 时间复杂度： O(N^2) 空间复杂度： O(1)
② 冒泡和插入相比谁更好？ 顺序有序一样好，接近有序插入好
- 快速排序
- 归并排序
- 计数排序
