排序

排序

1.基本概念

1.排序

1.排序，就是重新排列列表中的元素，使表中的元素满足按关键字有序的过程

2.排序算法的评价指标

1.时间复杂度

2.空间复杂度

3.稳定性：若待排序表中有两个元素Ri和Rj，其对应的关键字相同即keyi = keyj，且在排序前Ri在Rj前面，若使用某一排序算法后，Ri仍然在Rj的前面，则称这个排序算法是稳定的，否则称排序算法是不稳定的。

4.关键字相同的元素在排序之后相对位置不变，称为稳定排序

5.Q：稳定的排序算法一定比不稳定的好？A：不一定，要看实际需求

3.分类

1.内部排序：数据都在内存中；更多关注算法的时间，空间复杂度

2.外部排序：数据太多，无法全部放入内存；更多关注如何使读写磁盘的次数更少

2.插入排序

1.算法思想

每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中，直到全部记录插入完成。

（形象的例子：打麻将）

2.代码实现

//插入排序
void InsertSort(int arr[], int n){
  int i,j,temp;
  for(int i = 1; i < n; i++){
    if(arr[i] < arr[i - 1]){
      temp = arr[i];
      for(j = i - 1; j >= 0 && arr[j] > temp; --j){
        arr[j + 1] = arr[j];
      }
      //j要么是-1，或者是arr[j] < temp,所以要将temp插入arr[j + 1]的位置
      arr[j + 1] = temp;
    }
  }
}

3.算法效率分析

1.空间复杂度 O(1)

2.时间复杂度

主要来自对比关键字、移动元素；若有n个元素，则需要n-1趟处理

1）最好情况：已经有序、共n - 1 趟处理，每一趟只需要对比关键字1次，不用移动元素；因此最好时间复杂度为O(N)

2）最坏情况：逆序情况

第1趟：对比关键字2次，移动元素3次

第2趟：对比关键字3次，移动元素4次

……

第i趟：对比关键字i+1次，移动元素i+2次

……

最好时间复杂度O(N^2)

3.稳定排序

3.优化——折半插入排序

1.思路：先用折半查找找到应该插入的位置

2.原理：当前i前面的节点已经有序且顺序存储，因此可以使用折半查找

3.此处折半查找有可能是查找失败，因此需要分析折半查找的插入位置：

1）当low > heigh 时折半查找停止，应将[low, i - 1]内的元素全部右移，并将temp放到low所指位置

2）当可以查找成功时，即A[mid] = temp时，为了保证算法的稳定性，应继续在mid所指位置右边寻找插入位置，low = mid + 1，此时，在此查找发现查找失败，插入位置即为low所指的位置

3）当temp在i前面不存在，且大于前面所有的数字时，通过折半查找，最后low指针会指向i，并且low>heigh，此时便不需要进行移动元素

4）当temp比i前面的所有数字都小时，最终会导致heigh < low，因此同样将[low, i - 1]内的元素全部右移，将temp插入low所指的位置

4.代码

//插入排序优化——折半插入排序
void InsertSortBiSearch(int arr[], int n){
    if(n <= 0){
        //数组为空
        return;
    }
    int temp = 0;
    for(int i = 1; i < n; ++i){
        if(arr[i - 1] > arr[i]){
            temp = arr[i];
            //找
            int low = 0, heigh = i - 1;
            while(low <= heigh){
                int mid = low + (heigh - low)/2;
                if(arr[mid] == temp){
                    low += 1;               //保证插入排序的稳定性
                }
                else if(temp < arr[mid]){
                    heigh = mid - 1;
                }
                else{
                    low = mid + 1;
                }
            }
            //搬数据
            for(int k = i - 1; k >= low; --k){
                arr[k + 1] = arr[k];
            }
            arr[low] = temp;
        }
    }
}

5.优化后虽然比较关键字的次数减少了，但是移动元素的次数没变，整体来看时间复杂度依然是O(n^2)

4.对于链表的插入排序

对于链表进行插入排序，避免了移动元素，但是对比关键字的次数依然是O(N^2)数量级。整体来看时间复杂度依然是O(n^2)

3.希尔排序

是在原有插入排序的基础上进行了优化，如果插入排序基本有序，则排序有较好的执行效率。

1.算法思想

1、希尔排序：先追求表中元素部分有序，再逐渐逼近全局有序

2、将带排序表分割成若干形如L[i, i + d, i + 2d, i + 3d , ……]的特殊子表，对各个子表分别进行直接插入排序。缩小增量d，重复上述过程，直到d = 1 为止。

3.对于增量d的缩小，希尔本人的建议：每次将增量缩减一半

2.代码实现

//希尔排序
void ShellSort(int arr[], int n){
    if(n <= 0)
        return;
    for(int k = n/2; k > 0; k /= 2){
        for(int i = k; i < n; i++){
            if(arr[i - k] > arr[i]){
                int temp = arr[i];
                int j = 0;
                for(j = i - k; j >= 0 && arr[j] > temp; j -= k){
                    arr[j + k] = arr[j];
                }
                arr[j + k] = temp;
            }
        }
    }
}

3.算法性能

1.空间复杂度 O(1)

2.时间复杂度 和增量序列d1,d2,d3……的算则有关，目前无法用数学手段证明确切的时间复杂度

1）最坏时间复杂度为O(N^2)，当n在某个范围内时，可达O(N^1.3)

3.算法的稳定性

不稳定

4.适用性：仅适用于顺序表，不适用于链表，因为算法的实现基于随机访问

4.冒泡排序

基于“交换”的排序：根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置——冒泡排序+快速排序

1.算法思想

1.从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即A[i - 1] > A[i])，则交换它们，直到序列比较完。称这样过程为“一趟”冒泡排序。

2.每一趟结束，可以确定一个元素的位置

3.若某一趟排序没有发生交换，说明此时已经整体有序，这是冒泡排序优化的点

2.代码实现

//冒泡排序
void BubbleSort(int arr[], int n){
    if(n <= 0)
        return;
    for(int i = 0; i < n; ++i){
        bool flag = false;                  //表示元素是否交换
        //冒泡的精髓在于两层循环遍历是相反的过程
        //i之前的都已经有序，j > i, 将合适的元素放到合适的位置
        for(int j = n - 1; j > i ; --j){
            if(arr[j - 1] > arr[j]){
                int temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
                flag = true;
            }
        }
        if(!flag){
            //这一趟排序，没有交换元素，说明已基本有序
            return;
        }
    }
}

3.算法性能分析

1.稳定算法

2.空间复杂度 O(1)

3.时间复杂度

1）最好有序的情况下，O(n)

2）最坏逆序：比较次数 = (n - 1) + (n - 2) + …… + 2 + 1 = n*(n - 1)/2 = 交换次数；所以最坏时间复杂度为O(N^2)

3）平均时间复杂度 O(n^2)

4.冒泡排序适合用于链表排序

5.快速排序

基于交换的排序算法

1.算法思想

1、在待排序表[1,2,3,……,n]中任取一个元素作为基准（通常取首元素），通过一趟排序将待排序表划分为独立的两部分L[1,……,k - 1]和L[k + 1,……,n]，使得L[1,……,k - 1]中所有元素小于基准值，L[k + 1,……,n]中所有元素大于等于基准值。

2、将基准元素放在最终位置L(k)上，这个过程为一次“划分”。然后分别递归地对两个子表重复上述过程，直至每部分只有一个元素或空为止，即所有元素都放在了最终位置上。

2.代码实现

//快速排序
void QuickSort(int arr[], int n){
    if(n <= 0)
        return;
    QuickSortEntrance(arr, 0, n);
}
//快排递归入口 前闭后开区间 [begin,end)
void QuickSortEntrance(int arr[], int begin, int end){
    if(begin >= end)
        return;
    int index = QuickSortPartition(arr,begin, end);
    //处理index左边的子表
    QuickSortEntrance(arr, begin, index);
    //处理index右边的子表
    QuickSortEntrance(arr, index + 1, end);
}

//快速排序划分 前闭后开区间 [begin,end)
int QuickSortPartition(int arr[], int begin , int end){
    //基准值
    int temp = arr[begin];
    int left = begin, right = end - 1;
    //此处判断条件不能加=号，否则会陷入死循环
    while(left < right){

        while(right > left && arr[right] > temp) right--;
        arr[left] = arr[right];

        while(left < right && arr[left] < temp) left++;
        arr[right] = arr[left];
    }
    arr[left] = temp;
    return left;
}

3.算法效率分析

1.时间复杂度 O(n * 递归深度)

2.空间复杂度 O(递归层数)

3.若每一次选中的基准值可将待排序序列划分为均匀的两个部分，则递归深度最小，算法效率最高。

4.如果初始情况表是有序的，则选首元素作为基准值时会导致每次划分很不均匀；

4.优化思路

尽量选择可以把数据中分的基准元素

1.选头、中、尾三个位置的元素，取中间值作为基准元素

2.随机选取一个元素作为基准元素

5.稳定性

快速排序是不稳定的

一趟排序？？一次划分？？（问题暂时保留）

6.简单选择排序

属于选择排序，在每一趟待排序元素中选取关键字最小（或最大）的元素加入有序子序列

1.算法思想

每一趟在待排序元素中选择关键字最小的元素加入有序子序列

2.代码实现

//简单选择排序
void SelectSort(int arr[], int n){
    if(n <= 0)
        return;
    for(int i = 0; i < n; ++i){
        int min_index = i;
        for(int j = i + 1; j < n; ++j){
            if(arr[j] < arr[min_index]){
                min_index = j;
            }
        }
        if(i != min_index){
            swap(arr[i], arr[min_index]);
        }
    }
}

3.算法效率分析

1.空间复杂度 O(1)

2.时间复杂度O(N)

3.稳定性：不稳定

4.适用性：既可以用于顺序表，也可以用于链表

5.此算法执行效率不会因为所给排序序列的顺序而发生变化

7.堆排序

1.什么是堆

若n个关键字序列L[1……n]满足下面性质，则称为堆（Heap）

1.大根堆

根节点大于左右子树的节点

L(i) >= L(2i) 且 L(i) >= L(2i + 1) （1 <= i <= n/2）

2.小根堆

根节点小于左右子树的节点

L(i) <= L(2i) 且 L(i) <= L(2i + 1) （1 <= i <= n/2）

2.建立大根堆

1.思路：把所有非中断节点都检查一遍，是否满足大根堆的要求，如果不满足，则进行调整

2.检查当前节点是否满足根大于左右子树；如果不满足，将当前节点与更大的一个孩子互换

 //建立大根堆
void BuildMaxHeap(int arr[], int n){
    if(n <= 0)
        return;
    for(int i = n/2; i >= 0; --i){
        //调整子节点
        for(int j = i; j < n; ++j){
            int index = 2*j + 2;
            if(index < n && arr[index] > arr[j]){
                swap(arr[j],arr[index]);
            }
            index = 2*j + 1;
            if(index < n && arr[index] > arr[j]){
                swap(arr[j],arr[index]);
            }
        }
    }
}

void BuildMaxHeap2(int arr[], int n){
    if(n <= 0)
        return;
    for(int i = n/2; i >= 0; --i){
        int index = 0;
        for(int j = 2*i + 1; j < n; j = 2*index + 1){
            if(j + 1 < n && arr[j + 1] > arr[j]){
                index = j + 1;
            }
            else{
                index = j;
            }
            if(arr[(j - 1)/2] > arr[index])
                break;
            swap(arr[(j - 1)/2], arr[index]);
        }
    }
}

void BuildMaxHeap3(int arr[], int n){
    if(n <= 0)
        return;
    for(int i = n/2; i >= 0; --i){
        AdjustHeap(arr,i,n);
    }
}

//将根节点为k，长度为k的树调整为大根堆
void AdjustHeap(int arr[], int k, int len){
    int index = 0;
    for(int j = 2*k + 1; j < len; j = 2*index + 1){
        if(j + 1 < len && arr[j + 1] > arr[j]){
            index = j + 1;
        }
        else{
            index = j;
        }
        if(arr[(j - 1)/2] > arr[index])
            break;
        swap(arr[(j - 1)/2], arr[index]);
    }
}

3.基于大根堆排序

1.选择排序：每一趟在待排序元素中选取关键字最短的元素加入有序子序列

2.堆排序：每一趟将堆顶元素加入有序子序列（与待排序序列中最后一个元素交换)；并将待排序元素序列再次调整为大根堆

//堆排序
void HeapSort(int arr[], int n){
    //1.构建大根堆，升序
    BuildMaxHeap2(arr, n);

    int right = n - 1;
    while(right > 0){
        //2.将堆顶元素放到末尾
        swap(arr[0], arr[right]);
        //3.重新调整为待排序序列为大根堆
        AdjustHeap(arr, 0, right);

        right--;
    }
}

4.算法效率分析

1.建堆时间复杂度

关键字对比只和树高有关 O(N)

2.堆排序的时间复杂度

第一趟：树高 n - 1，对比次数->log(N-1)

第二趟：树高 n - 2，对比次数->log(N-2)

……

第N-1趟：树高 1，对比次数-> 0

所以堆排序的时间复杂度为O(NlogN)；

4.空间复杂度 O(1)

5.稳定性：堆排序是不稳定的；（原因是，如果左右子树的值相等，则会建堆，排序过程中，优先选择左子树的值放到堆顶，交换到末尾，导致左子树的值在右子树的后面）

6.大根堆：递增序列，小根堆，递减序列

5.小根堆排序

//堆排序
void HeapMinSort(int arr[], int n){
    //1.构建小根堆，降序
    BuildMinHeap(arr, n);

    int right = n - 1;
    while(right > 0){
        //2.将堆顶元素放到末尾
        swap(arr[0], arr[right]);
        //3.重新调整为待排序序列为小根堆
        AdjustMinHeap(arr, 0, right);

        right--;
    }
}

void BuildMinHeap(int arr[], int n){
    if(n <= 0)
        return;
    for(int i = n/2; i >= 0; --i){
        AdjustMinHeap(arr,i,n);
    }
}

//将根节点为k，长度为k的树调整为小根堆
void AdjustMinHeap(int arr[], int k, int len){
    int index = 0;
    for(int j = 2*k + 1; j < len; j = 2*index + 1){
        if(j + 1 < len && arr[j + 1] < arr[j]){
            index = j + 1;
        }
        else{
            index = j;
        }
        if(arr[(j - 1)/2] < arr[index])
            break;
        swap(arr[(j - 1)/2], arr[index]);
    }
}

6.堆的插入删除

1.插入

对于小根堆，新元素放到表尾，与父节点对比，若新元素比父节点更小，则将二者互换。新元素就这样一路上升，直到无法继续上升为止。

2.删除

对于小根堆，被删除的元素用堆低元素替代，然后让该元素不断下坠（大于左右子树的任一一个，与左右子树中更小的交换），直到无法下坠为止。

3.代码实现

下次再写，类似于AdjustHeap()

8.归并排序

1.什么是归并Merge

1、归并：把两个或多个已经有序的序列合并成一个

2、二路归并：每选出一个小元素注意需要对比关键字1次

3、M路归并：把M个已经有序的序列合并成一个，每选出一个小元素需要对比关键字M - 1次

2.归并排序

在内部排序中一般选择2路归并

核心操作：将两个有序序列合并成一个序列

//将两个有序子序列合并成一个子序列 [low , mid] [mid + 1, hegih]各自有序
void MergeSortedArray(int arr[], int low, int mid, int hegih){
    int *temp = (int*)malloc(sizeof(int)*(hegih - low + 1));
    //借助辅助数组
    for(int i = low; i <= hegih; ++i){
        temp[i] = arr[i];
    }
    //搬数据
    int index = low;
    int i = low, j = mid + 1;
    for(; i <= mid && j <= hegih; ){
        if(temp[i] < temp[j]){
            arr[index++] = temp[i++];
        }
        else{
            arr[index++] = temp[j++];
        }
    }
    while(i <= mid){
        arr[index++] = temp[i++];
    }

    while(j <= hegih){
        arr[index++] = temp[j++];
    }
    free(temp);
}

3.归并排序完整代码

//归并排序
void MergeSort(int arr[],int n){
    if(n <= 0)
        return;
    //均为闭区间
    MergeSortEntrance(arr, 0, n - 1);
}

//归并排序入口
void MergeSortEntrance(int arr[], int begin, int end){
    if(begin >= end)
        return;
    int mid = begin + (end - begin)/2;
    //类似于后序遍历
    MergeSortEntrance(arr, begin, mid);     //对左部分进行归并
    MergeSortEntrance(arr, mid + 1, end);   //对右部分进行归并
    MergeSortedArray(arr, begin, mid, end); //对已经有序的左右进行合并
}

4.算法效率分析

1.时间复杂度

2.空间复杂度

空间复杂度为O(n)，来自于辅助数组B

3.稳定性：稳定

9.基数排序

1.算法思想

1.第一趟：

1）以个位分配

2）收集

依次从个位值较大的队列开始收集

2.第二趟：

1）基于第一趟的收集结果，以十位进行分配

2）收集：类似于第一趟的收集

3.第3趟：

1）分配

2）回收

全局来看，得到一个有序的序列，递减

2.基数排序

不是基于比较的排序算法；

基数：每一位的取值范围，可以理解为“几进制"数，则基数是多少，即r为多少

如果想通过基数排序得到一个递增的序列，则只需要在收集的时候从代表基数值最小的队列开始即可；

从Q0 ~Q9收集：递增序列

从O9~Q0收集：递减序列

3.代码定义

5.基数排序的应用

分组可以具体问题具体分析，如在数值排序中，是按照个位、百位等进行分组；在学校学生排序过程中，按照年、月、日进行分组；

基数排序的使用场景就是r，d较小，n贼大的场景

10.外部排序

1.外存、内存之间的数据交换

1.操作系统以”块“为单位对磁盘存储空间进行管理，如：每块大小1KB，各个磁盘块内存放着各种各样的数据

2.磁盘的读/写以”块“为单位数据读入内存后才能被修改，修改完了还要写回磁盘。

2.外部排序的原理

1.数据元素太多，无法一次全部读入内存进行排序，使用”归并排序“的方法，最少只需要在内存中分配3块大小的缓冲区即可对任意一个大文件进行排序。

2.3块缓冲区，可分为：2个输入缓冲区，1个缓冲区

3.构造初始”归并段“,"归并排序”要求各个子序列有序，每次读入两个块的内容，进行内部排序后写回磁盘

3.归并排序的步骤

很难用语言组织，看王道课：https://www.bilibili.com/video/BV1b7411N798?p=87&spm_id_from=pageDriver

每当一个缓冲区空时，必须从外存读入，否则排序会出问题。

4.时间开销分析

1.生成初始归并段

2.第一趟归并

3.第二趟归并

4.第三趟归并

……

外部排序时间开销=读写外存的时间 + 内部排序所需时间 + 内部归并所需时间

5.优化

1.使用多路归并，设置多个输入缓冲区；每当一个缓冲区空，需要立即读入当前归并段的下一块的数据；

2.通过多路归并，可以减少归并的趟数，从而提高效率；相当于K叉树查找，K如果过大，则也会导致内存排序效率的降低，从K个段中选择一个最小的关键字，需要通过K - 1 次对比。（此问题可以通过败者树解决）

如果生成初始归并段的“内存工作区”越大，初始归并段越长，则排序所需要的r归并段数量越少，相应的效率也会提高。

3.总结

6.K路平衡归并

1.最多只能有k个段归并为一个；

2.每一趟归并中，若有m个归并段参与归并，则经过这一趟处理得到m/k个新的归并段

7.外部排序遗留问题——个人不理解点

Q：归并段如何在外存中存储，实现归并段不同块之间的顺序读取？

Q：通过文件描述符，可以实现对外存文件的顺序读取，那对于整个文件来说，需要实现多路归并，是否需要保存多个文件描述符（当前文件描述符所指文件的多个划分为归并段的不同起始位置）？

Q：如果多个归并段的不同起始位置需要存储，该如何存储？数据结构如何实现？

A：待细细考证

11.败者树

1.多路平衡归并带来的问题

外部排序时间开销 = 读写外存时间 + 内部排序时间 + 内部归并所需时间

11.败者树

1.多路平衡归并带来的问题

外部排序时间开销 = 读写外存时间 + 内部排序时间 + 内部归并所需时间

2.败者树概念

败者树，可视为一颗完全二叉树。k个叶节点分别是当前参加比较的元素，非叶节点用来记忆左右子树中的”失败者“，而让胜者往上继续进行比较，一直到根节点。

3.过程

4.代码实现思路

5.问题

Q：败者树为什么能取到最小值？

A：首次构建败者树，比较k-1次，可以选出最小值，当最小值被取走之后，位置空缺，则选择该最小值所在的归并段的元素填充，依次进行比较，所以最多比较树的高度次，无论如何，都可以找到最小值

12.置换-选择排序

1.多路归并带来的问题

外部排序时间开销 = 读写外存时间 + 内部排序时间 + 内部归并所需时间

1.如果可以减少初始归并段的数量r，可以有效减少归并的趟数，从而提高效率

2.构造初始归并段老方法

用一片比较大的内存空间区域来进行内部排序，但是如果内部空间可以容纳l个记录，则么个初始归并段也只能容纳l个记录，若文件有n个记录，则初始归并段的数量r = n/l;

此种方法构造的初始归并段大小长度一致

3.构造比内存空间大的初始归并段

13.最佳归并树

1.引入原因

1、使用置换选择排序生成的初始归并段，长度大小不一致。

2、这就出现了一个问题，如下图

2.构造2路归并的最佳归并树

如果采用顺序归并，因为选择置换生成的归并段长度不一致，因此可能导致没必要的重复读写操作，导致I/O次数增加，降低排序效率，因此可以通过归并树，可以很有效的降低I/O次数，提升效率

3.多路归并

1.顺序归并，需要读写的磁盘I/O次数如下：

2.多路归并的最佳归并树

选择N个值最小的节点作为兄弟，其和作为新的节点，依次递归构建，如下图

3.如果归并段的数量n - 1不能整除k(k路归并)