排序
1.排序的定义
排序：所谓排序，就是使用一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作
稳定性：根据在排序过程中没有间隔或者插入就是稳定
内部排序：数据元素全部放在内存中的排序
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不饿能在内外村之间移动的数据
2.插入排序
思想：找待插入元素的位置 插入到 end+1 的位置
2.1直接插入排序
应用场景：数据接近有序或者数据量小
接近有序：小的数据尽量靠前，大的数据尽量靠中间
时间复杂度：O(N2)
空间复杂度：O(1)
稳定性：稳定
最差时间复杂度：O(N2)
//七种常见的排序算法----->插入排序
public static void insertSort(int[] array){
//外层循环--->取到数组中的每一个元素，进行插入
for (int i = 1; i < array.length; i++) {
//将元素插入到序列中
//k表示要插入元素的值
//end表示要移动的元素的下标
int k = array[i];
int end = i - 1;
while(end >= 0 && k < array[end]){
array[end + 1] = array[end];
end--;
}
//表示要么这个元素是最小的，要么比end位置的元素大
array[end + 1] = k;
}
}
2.2 希尔排序
基本思想：
1.选定一个整数 gap 把排序文件中的所有记录分成组，对每一个组内的记录进行排序
2.当 gap 为1 时，所有记录在在同一组内排好序
3.当 gap > 1时为预排序
4.希尔排序是对直接插入排序的优化
应用场景：数据量多，比较凌乱而且随机
时间复杂度：不好确认，与gap的取值有关
空间复杂度：O(1)
稳定性：不稳定
最差时间复杂度：O(N2)
//希尔排序
public static void ShellSort(int[] array2) {
int gap = 3;
//规定gap = 3，直到gap = 0
while(gap > 0 ){
for(int i = 1;i< array2.length;i++){
int k = array2[i];
int end = i - gap;
while(end >= 0 && k < array2[end]){
array2[end + gap] = array2[end];
end -= gap;
}
array2[end + gap] = k;
}
gap --;
}
}
3.选择排序
基本思想：
1.在序列中找最大的位置
2.将该位置上的元素与区间最后一个元素惊醒交换
3.1 直接选择排序
- 在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素
- 若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换
- 在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素
应用场景：直接选择排序思想非常好理解，但是效率不是很好，很少使用
时间复杂度：O(N2)
空间复杂度：O(1)
稳定性：不稳定
缺陷：会重复比较
public static void selectSort(int[] array){
//进行的趟数
int end = array.length - 1;
while(end >= 0){
//对找到的最大元素进行标记，初始值给为0，每次从最开始的位置开始寻找
int pos = 0;
//进行查找最大元素的过程
for (int i = 0; i <= end; i++) {
if(array[pos] < array[i]){
pos = i;
}
}
//判断pos的位置，如果不是，就进行交换
if(pos != end){
int temp = array[pos];
array[pos] = array[end];
array[end] = temp;
}
end--;
}
}
4.堆排序
基本思想：
1. 排升序建大堆，排降序建小堆
- 找倒数第一个非叶子节点（sin - 1-1）/2
- 从倒数第一个非叶子节点倒这往根
2. 利用堆删除的思想
- 用堆顶元素与在、堆中最后元素交换
- 将堆中有效元素减少一个
- 将堆中元素向下调整
应用场景：需要一个序列中前k个最大 || 最小，可能会和其他的排序复合起来提高排序的效率
时间复杂度：O(N*logN)
空间复杂度：O(1)
稳定性：不稳定
//利用堆删除的思想
public static void shiftDown(int[] array,int size,int parent){
int child = parent * 2 + 1;
while(child < size){
if(child + 1 < size && array[child] < array[child + 1]){
child = child + 1;
}
if(array[parent] < array[child]){
int temp = array[parent];
array[parent] = array[child];
array[child] = temp;
parent = child;
child = parent * 2 + 1;
}else{
return;
}
}
}
//实现堆排序的方法
public static void heapSort(int[] array){
int size = array.length;
int parent = ((array.length - 2) >> 1);
//对堆里的非叶子结点进行排序，使得交换时的堆除了堆顶元素，均为有序的堆
for (int root = parent; root >= 0; root--) {
//从第一个非叶子结点进行向下调整
shiftDown(array,size,root);
}
int end = size - 1;
while(end != 0){
//交换第一个和最后一个元素
int temp = array[0];
array[0] = array[end];
array[end] = temp;
//从堆中删除一个元素后进行调整
shiftDown(array,end,0);
end--;
}
}
5.交换排序
基本思想：根据一个序列中记录两个记录键值的比较结果来对换这两个记录在序列中的位置
交换排序的特点 : 将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动
5.1 冒泡排序
时间复杂度：O(N2)
空间复杂度：O(1)
稳定性:稳定
//依次比较，向后移动
public static void bubbleSort(int[] array){
int size = array.length;
//需要冒泡的趟数
for (int i = 0; i < size - 1; i++) {
//需要对数组进行比较
for (int j = 0; j < size - 1; j++) {
if(array[j] > array[j + 1]){
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
5.2 快速排序
基准值：从代码可行性上，一般取的区间两侧的数据
基本思想 找一个基准值，将其分割成两部分，左侧小于基准值，右侧大于基准值 分析快排性能 如果序列有序或接近有序，每次取到基准值是区间的max 和 min 划分好了 基准值一侧有数据，一侧无数据
时间复杂度： O（NlogN）
最坏时间复杂度：O（N2）
应用场景：因此快排不适合有序或接近有序的场景排序，数据非常随机且凌乱（如果序列比较随机，数据比较凌乱，每次基准值取得比较理想，划分之后，基准值左右两侧数据基本均等===》所画的图为平衡二叉树O(NlogN)）
5.2.1 Hoare版
基本思路：
- 让begin在最左侧，让end在最右侧，当基准值选在最右侧时 begin先走，当遇到第一个比基准值大的元素，停下来
- end再走，当遇到第一个比基准值小的停下来 两个元素进行交换，当这一趟循环走完时，begin和end在同一位置
3.只需用将此时的begin或end和数组最后的一个元素进行交换，就可以让基准值在中间位置
public static int partition1(int[] array,int left,int right){
int index = getMidIndex(array,left,right);
if(index != right - 1){
swap(array,index,right - 1);
}
int key = array[right - 1];
int begin = left;
int end = right - 1;
//基准值取在右侧，因此begin先走，找比基准值大的元素
while(begin < end){
while(begin < end && array[begin] <= key){
begin++;
}
//end再走，找比基准值小的，并停下来
while(begin < end && array[end] >= key){
end--;
}
//如果begin和end在同一个位置就不用交换了
if(begin != end){
swap(array,begin,end);
}
}
//当begin和end走到同一个位置时，和此时数组的最后一个元素交换位置
swap(array,begin,right - 1);
return begin;
}
5.2.2 挖坑法
基本思想
1. 先将基准值处的值取出并标记，这就变成一个坑
2. 从begin开始，当遇到一个比基准值大的元素，就放到这个坑的位置
3. 因此，begin此时也是一个坑，就让end从最后一个元素的进行查找
4. 如果遇到一个比基准值小的，就放到之前begin的位置以此类推
5. 当begin和end相遇，用标记的基准值填坑
public static int partition2(int[] array,int left,int right){
int index = getMidIndex(array,left,right);
if(index != right - 1){
swap(array,index,right - 1);
}
int key = array[right - 1];
int begin = left;
int end = right - 1;
while(begin < end){
//寻找比基准值大的元素，当遇到比基准值大的元素时，停下来
while(begin < end && array[begin] <= key){
begin++;
}
//判断是否begin和end相等，如果不相等，就交换
if (begin < end){
array[end] = array[begin];
}
//寻找比基准值小的元素，当遇到比基准值小的元素时，停下来
while(begin < end && array[end] >= key){
end--;
}
if(begin < end){
array[begin] = array[end];
}
}
//此时已经找完了，就让begin处放上标记值
array[begin] = key;
return begin;
}
5.2.3前后指针
public static void quickSortNonr(int[] array,int left,int right){
Stack<Integer> s = new Stack<>();
s.push(left);
s.push(right);
while(!s.empty()){
right = s.pop();
left = s.pop();
if(right - left > 1){
int div = partition1(array, left, right);
//将区间分为了[left,div)和[div + 1,right)
s.push(div + 1);
s.push(right);
s.push(left);
s.push(div);
}
}
}
6.快速排序优化
6.1 三数取中法
优化基准值的方式：不从两侧取值
一次性取三个数字：最左一个 最右一个 最中间一个 ------>以这三个数据中的中间数字作为基准值
mid = left + (( right - left ) >> 1 )
时间复杂度：O（N*logN）
空间复杂度： O（logN）
稳定性： 不稳定
应用场景： 数据越随机越nice
public static int getMidIndex(int[] array,int left,int right){
int mid = left + ((right - left) >> 1);
//判断三个数当中最大的一个数
if(array[left] < array[right - 1]){
//比最小的小，返回left
if(array[mid] < array[left]){
return left;
}else if(array[mid] > array[right - 1]){
//比最大的大，返回right - 1；
return right - 1;
}else{
return mid;
}
}else{
if(array[mid] < array[right - 1]){
return right - 1;
}else if(array[mid] > array[left]){
return left;
}else{
return mid;
}
}
7.归并排序
基本思想：每次对区间进行均分，均分到一定程度，发现区间中的数据有序，再进行合并
时间复杂度： O（N*logN）
空间复杂度： O（N）
稳定性： 稳定
//基本思想：就是利用不断递归，借用辅助空间让原数组一部分先有序，在复制到原数组当中去
public static void mergeDate(int[] array,int left,int mid,int right,int[] temp){
//这可以看做是两个数组
//这是第一个数组的边界 begin1 end1
int begin1 = left;
int end1 = mid;
//这是第二个数组的边界 begin2 end2
int begin2 = mid;
int end2 = right;
//这是临时数组的且我们需要的边界的起始下标
int index = left;
//对两个数组进行的元素进行合并
while(begin1 < end1 && begin2 < end2){
if(array[begin1] <= array[begin2]){
temp[index] = array[begin1];
index++;
begin1++;
}else{
temp[index] = array[begin2];
index++;
begin2++;
}
}
//判断是哪个数组先排完（上面的合并过程并不能保证每一个数组都是均等的）
while(begin1 < end1){
temp[index] = array[begin1];
index++;
begin1++;
}
while(begin2 < end2){
temp[index] = array[begin2];
index++;
begin2++;
}
}
7.各大排序万能总结
