1、冒泡排序
1）基本思想：在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。
判断排序结束的条件应该是“在一趟排序过程中没有进行记录交换的操作”。
受初始序列的顺序影响：若初始序列有序，在第一趟冒泡后就跳出循环了，仅需比较n-1次且无数据交换
若初始为逆序，则需进行n-1次冒泡，比较次数为n(n-1)/2,移动次数为3n(n-1)/2
2）java实现
//冒泡排序
public void bubbleSort(int[] arr){
for(int i = 0; i < arr.length; i ++){
boolean flag = false;
for(int j = arr.length - 1; j > i ; j --){
if(arr[j] > arr[j-1]){
int temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
flag = true
}
}
if(flag == false)
return;
}
System.out.print("冒泡排序：");
print(arr);
}
2、快速排序
基于分治的思想，因为需要递归，需要栈来存放每一层递归调用的必要信息（在处理一个子区间时，保存另一个子区间的上下界）
在将原序列进行划分时，最理想的是平分，此时运行速度将大大提升
1）基本思想：
受初始序列的顺序影响：因为快排的运行效率与划分是否对称有关，而后者又与选择以哪一个元素进行划分有关，最坏情况发生在两个区域分别包含n-1个和0个元素时。
若初始正序或者逆序时，运行时间为O(n2),栈的深度为O(n),
2）java实现
//快速排序
public void quickSort(int[] arr){
quick(arr,0,arr.length - 1);
System.out.print("快速排序：");
print(arr);
}
public int[] quick(int[] arr,int low, int high){
if(low < high){
int middle = getMiddle(arr,low, high);
quick(arr, low, middle-1);
quick(arr, middle+1, high);
}
return arr;
}
public int getMiddle(int[] arr, int low, int high){
int temp = arr[low];
while(low < high){
while(low<high && arr[high] < temp)
high --;
arr[low] = arr[high];
while(low<high && arr[low] > temp)
low ++;
arr[high] = arr[low];
}
arr[low] = temp;
return low;
}
3、选择排序
若初始序列有序，比较次数不受影响，第i趟找最小元素需要比较n-i次，但是移动次数有影响，若为正序，移动次数为0，若为逆序，移动总次数为3（n-1)
1）基本思想：每次遍历过程中找到最小的一个元素的下标，将最小的元素与未排序的那部分序列的最前面一个元素交换
2）java实现
//选择排序
public void selectionSort(int[] arr){
for(int i = 0; i < arr.length; i ++){
int maxIndex = i;
for(int j = i+1; j < arr.length; j ++){
if(arr[maxIndex] < arr[j])
maxIndex = j;
}
int temp = arr[maxIndex];
arr[maxIndex] = arr[i];
arr[i] = temp;
}
System.out.print("选择排序：");
print(arr);
}
4、插入排序
1）基本思想：：每次将一个待排序的记录，按其大小插入到前面已经排序的子序列的合适位置，直到全部插入
直接插入排序：首先认为第一个元素是排好序的，然后剩余元素按顺序查找法插入到已排好序的合适位置
初始排序有影响：正序时，总的比较次数为n-1，移动次数为0；逆序时，总的比较次数和移动次数最好
折半插入排序：首先认为第一个元素是排好序的，然后剩余元素按折半查找法插入到已排好序的合适位置
比较次数不受初始排序的影响，仅取决于序列中的元素个数n
在直接插入排序中，总是边比较边移动元素，而折半插入排序则是将比较和移动操作分离，即先查找出元素的待插入位置，然后再统一地移动待插入位置之后的所有元素。
希尔排序：先将待排序序列分割成若干个形如L[i, i+d, i+2d,…i+kd]的“特殊”子表，分别进行直接插入排序，当整个表中元素已成“基本有序”时，在对全几率进行一次直接插入排序。
2）java实现直接插入排序
//插入排序
public void insertSort(int[] arr){
for(int i = 1; i < arr.length; i ++){
for(int j = i; j > 0 && arr[j] > arr[j-1]; j -- ){
int temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
}
}
System.out.print("插入排序：");
print(arr);
}
5、堆排序：
基本思想：先按给定序列的顺序写出完全二叉树，然后从倒数第一个非叶子结点开始调整为大顶堆或者小顶堆，一直往上调整到树根。
不受初始序列的排序影响
大顶堆：父节点的值大于左右子节点的值
小顶堆：父节点的值小于左右子节点的值
6、二路归并排序
基本思想：将两个或者两个以上的有序表组合成一个新的有序表。嘉定排序表含有n个元素，则可以看成n个有序子表，每个子表长度为1，然后两两归并，得到n/2个长度为2或1的有序表，再进行两两归并—-如此重复，直到合并成一个有序表为止。
一般而言，对于N个元素进行k路归并排序时，排序的趟数m满足k的m次方等于n，从而m=logk n（以k为底）。
不受初始序列的排序影响
*************************************************************************************************************************************
不同排序算法的比较：
|
算法种类 |
时间复杂度 |
空间复杂度 |
是否稳定 |
||
|
最好情况 |
平均情况 |
最坏情况 |
|||
|
直接插入排序 |
O(n) |
O(n2) |
O(n2) |
O(1) |
是 |
|
冒泡排序 |
O(n) |
O(n2) |
O(n2) |
O(1) |
是 |
|
简单选择排序 |
O(n2) |
O(n2) |
O(n2) |
O(1) |
否 |
|
希尔排序 |
|
|
|
O(1) |
否 |
|
快速排序 |
O(nlogn) |
O(nlogn) |
O(n2) |
O(logn) |
否 |
|
堆排序 |
O(nlogn) |
O(nlogn) |
O(nlogn) |
O(1) |
否 |
|
二路归并排序 |
O(nlogn) |
O(nlogn) |
O(nlogn) |
O(n) |
是 |
|
基数排序 |
O(d(n+r)) |
O(d(n+r)) |
O(d(n+r)) |
O(r) |
是 |
原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/13771.html