排序
排序的概念
排序：按照从小到大或从大到小的顺序排序
稳定性：如果在排序后两个相同数字在排序后仍是前后顺序这个算法就称为稳定的，否则不稳定。
内部排序：数据元素全部放在内存中的排序
外部排序：数据元素太多不能同时放在内存中，可能就在D盘E盘中进行的排序，排序过程中不能在内外之间移动数据。
排序的运用
排序可以快速将一个商品按照客户所指定的目标排序，像线上购物可以按照用户购买量排序，也可以按照物品的价格排序等等，这个排序可以让用户更快更准确购买商品。又或者是成绩排序，可以更好的了解学生近日的学习情况等消息。
常见的排序算法实现
直接插入排序
直接插入排序简称插入排序，是直接在数组中进行排序，通过两个指针一起使用，前指针负责比较，后指针则负责记录位置。基本思路就是： i 现在1的下标记录数值并使用局部标量记录 i 下标的值，然后 j 下标在 i-1 下标下比较，如果不符合从小到大的准则（默认从小到大，大家也可以按照自己的规则进行调整呦~）那就需要进行调换将 j 的数值放在 j+1 的位置下，符合就直接跳出循环即可。 j 层循环结束后还需要把temp的数放在 j+1 的下标下。
插入排序的时间复杂度最好是本身有序的（O(N)），最坏情况下就是相反每一个都没顺序（O(N^2)），在排序的过程中只开辟了一个空间，所以空间复杂度即为O(1)。关于稳定性，插入排序是一个稳定的排序，对于一个稳定的排序，是可以实现不稳定的排序的，但是一个本身就不稳定的排序是无法实现稳定的排序的。
public static void insort1(int[] arr) {
for (int i = 1; i < arr.length; i++){
int temp = arr[i];
int j = i-1;
for (; j >= 0; j--){
if (temp < arr[j]){
arr[j+1] = arr[j];
}else{
break;
}
}
arr[j+1] = temp;
}
}
希尔排序
希尔排序也称缩小增量排序，将数组分成数组长度的一半组，然后对每一个组进行排序。假设一组有10个元素就要分成5组，并且这5组可以分成两组的第n个为一组，如下图。第一次排序完数组中较小的数几乎都在前面，每一此分组都 除以2 将每一组都排序，除了分成 1 组外其他的排序都是预排序，最后一次排序才是结果。
希尔排序的时间复杂度是O(N^1.3~N^1.5)，空间复杂度是O(1)，并且它是不稳定的排序，交换两个数可能导致相同的两个数顺序不一样。
public static void shell(int[] arr){
int gap = arr.length;
while (gap > 1){
gap /= 2;
part(arr, gap);
}
}
private static void part(int[] arr, int gap){
for (int i = gap; i < arr.length; i++){
int ret = arr[i];
int j = i - gap;
for (; j >= 0; j -= gap){
if (arr[j] > ret){
arr[j+gap] = arr[j];
}else{
break;
}
}
arr[j+gap] = ret;
}
}选择排序
选择排序就是每一次将数组中最小的数据放在前面，直至数组遍历完。设置 i 方便记录此时数组值的大小，并赋值 i 下标为最小值min，然后再从 i 后开始遍历每一个值，每当有一个比数组 i 下标的还更小的就把小的值给min，直到数组遍历完停止，然后就将最小值min的下标与 i 交换，此时下标就是从 i 往后最小的，循环这个操作，这个数组就是排好顺序了。
选择排序的时间复杂度是O(N^2)，每一次都需要遍历 i 后的所有值，其空间复杂度是O(1)。它需要交换两个值的顺序，所以当存在两个下标的值相同时，可能会改变这两个值得顺序，所以选择排序是不稳定的。
private static void swap(int[] arr, int i, int j){
int ret = arr[i];
arr[i] = arr[j];
arr[j] = ret;
}
public static void select11(int[] arr){
for (int i = 0; i < arr.length; i++){
int min = i;
for (int j = i+1; j < arr.length; j++){
if (arr[j] < arr[min]){
min = j;
}
}
swap(arr, min, i);
}
}如果使用两个指针排序，那就得是前后两指针，结束条件就是前指针不能超过后指针。设置两个最值一个最大一个最小，前指针位置就是开始位置往后遍历找最大最小值，当数组遍历完时循环内层循环停止，并交换前指针放最小值，后指针放最大值，要注意如果最大值在前指针时将前指针和最小值交换时，最大值就会被改变成最小值，所以要注意当最大值等于前指针时需要将调换后的最小值给最大值，然后两指针往中间移。
public static void select2(int[] arr){
int left = 0;
int right = arr.length-1;
while (left < right) {
int min = left;
int max = left;
for (int i = left; i <= right; i++){
if (arr[i] < arr[min]){
min = i;
}
if (arr[i] > arr[max]){
max = i;
}
}
swap(arr, left, min);
if (max == left){
max = min;
}
swap(arr, right, max);
left++;
right--;
}
}堆排序
堆排序建堆的原则是：升序建大堆，降序建小堆。（把最大的值与最后一个值交换）
首先我们先设计一个大堆使用向下调整法，从最后一个元素的父结点开始往前遍历直到结点小于0，每次都要调正堆使其满足大根堆，先找到孩子结点中最大的再与父结点比较如果孩子结点更大就需要交换两者并且需要向下调整（判断调换后的是否每个子堆都满足大根堆），所以将孩子结点赋给父结点，再用同样方法找孩子结点最大的再比较，循环条件就是这个父结点没有孩子结点，也就是孩子结点不能大于数组下标。这个大根堆就创建完成，然后就是排序，将大根堆的根结点与数组最后一个下标交换，然后再调整剩下的，然后下标前移。
堆排序的时间复杂度是O（N*logN），向下调整的复杂度是O(logN)，空间复杂度是O(1)。它是不稳定的排序。
public static void heapsort(int[] arr){
creatheap(arr);
int end = arr.length - 1;
while (end>0){
swap(arr, 0, end);
shifdown(arr, 0, end);
end--;
}
}
private static void shifdown(int[] arr, int p, int end){
int c = 2*p+1;
while (c < end) {
if ( c + 1 < end && arr[c] < arr[c + 1] ) {
c++;
}
if (arr[c] >arr[p]) {
swap(arr, p, c);
p = c;//
c = 2*p+1;
}else{
break;
}
}
}
public static void creatheap(int[] arr){
int end = arr.length - 1;
for (int p = (end - 1)/2; p >= 0; p--){
shifdown(arr, p, arr.length);
}
}冒泡排序
冒泡排序就是将最大的值放在最后，依次从头开始遍历，每一次外层循环是将最大值放到最后，内部循环是找最大值出来，找到最大就放到当前加1的位置接着循环比较，当找到倒数第二个时倒数第一个就不用找了，所以找内部循环需要减少一次。如果使用布尔类型可以优化算法，可以更快排序。
冒泡排序的时间复杂度是O(N^2)，如果加了优化最好情况下是O(N)，空间复杂度是O(1)。它是一个稳定排序。
public static void bubblesort(int[] arr){
for (int i = 0; i < arr.length; i++){
boolean flag = false;
for (int j = 0; j < arr.length - 1 - i; j++){
if (arr[j] > arr[j+1]) {
swap(arr, j+1, j);
flag = true;
}
}
if (!flag){
break;
}
}
}快速排序
快速排序hoare版区别在与将前后两指针遇到不符合的两者交换，最后结束key与left交换得到数组大小的中心位置，然后再用递归的方法分别比较两边，如果前后指针越界了就停止。
//快速排序hoare
public static void quicksort(int[] arr) {
quick(arr, 0, arr.length -1);
}
private static void quick(int[] arr, int left, int right){
if (left >= right)
return ;
int center = quickcenter(arr, left, right);
quick(arr, left, center - 1);
quick(arr, center + 1, right);
}
private static int quickcenter(int[] arr, int left, int right){
int key = arr[left];
int i = left;
while (left < right){
while(left < right && arr[right] >= key){
right--;
}
while (left < right && arr[left] <= key){
left++;
}
swap(arr, left, right);
}
swap(arr, i, left);
return left;
}快速排序挖空版主要在于取出第一位置的元素，从后指针开始遇到小于key的元素就将该值放在前指针上，并从前指针开始找遇到大于key的元素就将这个值放在后指针，就这样一前一后直到两个指针相遇时循环结束。这就是这个与hoare版的最大区别。
private static int quickcenter(int[] arr, int left, int right){
int key = arr[left];
while (left < right){
while(left < right && arr[right] >= key){
right--;
}
arr[left] = arr[right];//把前指针覆盖
while (left < right && arr[left] <= key){
left++;
}
arr[right] = arr[left];//把后指针覆盖
}
arr[left] = key;//把key赋给中间交接处
return left;
}快速排序前后指针版主要在于两指针都再一边（属于两指针相邻的），如果满足后指针小于left下标的元素并且满足前指针+1后与后指针相同（意思就是前后指针相邻没有间隔）前后指针交换，然后后指针不管如何都++，当后指针超过数组长度时循环结束，最后将left与前指针的值交换。
private static int quickcenter2(int[] arr, int left, int right){
int pre = left;
int cur = left+1;
while (cur < arr.length){
if (arr[cur] < arr[left] && arr[++pre] == arr[cur]){
swap(arr, pre, cur);
}
cur++;
}
swap(arr, pre, left);
return pre;
}前面全是递归法，接下来讲非递归法：
快速排序非递归法先通过左右端元素找基准，然后找将左右两边的前后端放入栈中（放入栈中必须要满足条件基准的左右两边必须要有两个元素以上才能进栈，如果没有两个元素就不需要进栈），再从栈中取出两个元素第一个放在后右边，然后放左边，然后再按照之前的方法找左右端的基准又用相同方法进栈。直至栈中元素为空循环结束。
//快速排序非递归
public static void quicksort2(int[] arr){
Stack<Integer> stack = new Stack<>();
int left = 0;
int right = arr.length - 1;
int center = quickcenter2(arr, left, right);//找基准
if (center - 1 > left){
stack.push(left);//将基准左边的前后元素放进栈中，如果左右边只有1个就不进入
stack.push(center - 1);
}
if (center + 1 < right){
stack.push(center + 1);//将基准左边的前后元素放进栈中
stack.push(right);
}
while (!stack.isEmpty()){
right = stack.pop();//先出栈的给右边，后出栈的给左边
left = stack.pop();//qu
center = quickcenter(arr, left, right);//再找基准，直到数组中元素基本遍历完
if (center - 1 > left){
stack.push(left);
stack.push(center - 1);
}
if (center + 1 < right){
stack.push(center + 1);
stack.push(right);
}
}
}对于快速排序来说不管哪种方法它的时间复杂度都是O(N*logN)，空间复杂度就是O(logN)（即二叉树的高度）。并且它也是一个不稳定的排序。
归并排序
归并排序是将一组数据先分解再合并成一个有序数组。分解是需要将每次分成左右两组并递归直至将每组元素分成一个一个的就停止（先递归左边再递归右边）；合并是归并排序的主要代码，他需要将每个单个的元素排序合成一个有序数组，然后再逐步往回返合并两个有序数组并放在一个大小相同的数组种暂存，最后等这一组数据都合并完成再将暂存在数组中的数据依次放在原先数组中，这样归并排序就结束了。
归并排序的时间复杂度是O(N*logN)，空间复杂度是O(N)。并且它是一个稳定的排序，可以修改大小符号改变稳定性。
public static void mergesort(int[] arr){
mergesortFunc(arr, 0, arr.length-1);
}
private static void mergesortFunc(int[] arr, int left, int right){
if(left >= right)
return;
int mid = (right + left) / 2;
mergesortFunc(arr, left, mid);
mergesortFunc(arr,mid+1, right);
merger(arr, left, right, mid);
}
private static void merger(int[] arr, int left, int right, int mid){
int s1 = left;
int s2 = mid + 1;
int[] temp = new int[right-left+1];
int k = 0;
while (s1 <= mid && s2 <= right){
if(arr[s2] <= arr[s1]){
temp[k++] = arr[s2++];
}else {
temp[k++] = arr[s1++];
}
}
while (s1 <= mid){
temp[k++] = arr[s1++];
}
while(s2 <= right){
temp[k++] = arr[s2++];
}
for (int i = 0; i < temp.length; i++){
arr[i+left] = temp[i];
}
}归并排序非递归法
private static void merge(int[] arr, int left, int right, int mid){
int s1 = left;
int s2 = mid + 1;
int[] temp = new int[right-left+1];
int k = 0;
while (s1 <= mid && s2 <= right){
if(arr[s2] <= arr[s1]){
temp[k++] = arr[s2++];
}else {
temp[k++] = arr[s1++];
}
}
while (s1 <= mid){
temp[k++] = arr[s1++];
}
while(s2 <= right){
temp[k++] = arr[s2++];
}
for (int i = 0; i < temp.length; i++){
arr[i+left] = temp[i];
}
}
public static void mergesortnor(int[] arr){
int gap = 1;
while (gap < arr.length){
for (int i = 0; i < arr.length; i += 2*gap){
int left = i;
int mid = left + gap - 1;
int right = mid + gap;
if (mid >= arr.length){
mid = arr.length - 1;
}
if (right >= arr.length){
right = arr.length - 1;
}
merge(arr, left, right, mid);
}
gap *= 2;
}
}
以上是所有的排序算法，还有一些排序只需要了解即可，大家下节再见呀！