经典排序算法与STL

排序算法

按照是否将元素放入到内存中，排序分为内部排序和外部排序。内部排序适合元素不多的文件，按照元素的排序原则，内部排序分为：

插入排序
交换排序
选择排序
归并排序

插入排序

基本方法是：寻找一个指定元素在待排序元素中的位置，然后将它插入

直接插入

基本思想：每次将一个待排序的元素按其关键码的大小插入到一个已经排好序的有序序列中，知道全部元素排序好。

void insert_sort(int arr[], int len){
 for (int i=1; i<len; i++) {
    int temp = arr[i] ;
    for (int j = i-1; j>=0; j--) {
      //j+1位置一直是空的，
        if (arr[j]>temp) {
            arr[j+1] = arr[j] ;
        }else {
            arr[j+1] = temp ;
            break ;
        }
    }
    
  }

 }

直接插入的两个特点：基本有序的序列，直接插入最快。记录个数很少的无序序列，直接插入也很快

希尔排序

希尔排序是对直接插入排序的一种改进。它的基本思想是：将待排序的元素分成多个子集，分别对这些子集进行直接插入排序，待整个序列都有序时，再对元素进行一次直接插入排序。

void Sort::shell_sort(int arr[] ,int len) {
//增长区间
for (int d = len /2; d>=1; d = d/2)
{   //一次希尔排序
    for (int i = d; i < len; i++)
    {    //和有序的数组的最后一个元素比较
        if (arr[i]<arr[i-d])
        {
            int temp = arr[i] ;
            int j = i-d ;
            while(j>=0&&arr[j]>temp){
                arr[j+d] = arr[j];
                j = j-d;
            }
            arr[j+d] = temp ;
        }
    }
}

}

交换排序

交换排序的基本方法是：在待排序的元素中选择两个元素，将他们的关键码进行比较，进行排序。

冒泡排序

基本思想是：两两比较相邻的元素，如果反序，则交换位置，直到没有反序的元素为止。

void bubble_sort(int arr[], int len){
//从小到大
for (int i = 0; i<len; i++) {
    for (int j = len-1; j>i; j--) {
        if (arr[j]<arr[j-1]) {
            int temp = arr[j] ;
            arr[j] = arr[j-1] ;
            arr[j-1] = temp ;
        }
    }
}    
}

快速排序

快速排序是冒泡排序的改进算法，快速排序元素的比较设移动是序列的两端到中间进行的。它的基本思想是：
在分区中选择一个元素为轴值，将待排序的元素划分为两个分区，左侧元素的关键码都小于或者等于轴值，右侧元素的关键码的值都大于或者等于轴值。重复上述过程，直到整个序列有序。

void quick_sort(int arr[], int left, int right){
//递归结束条件
if (left<right) {
    //一次遍历
    int i = left , j = right , key = arr[left] ;
     while (i<j) {
        while (i<j&&arr[j]>key) 
        j-- ;
        if (i<j)
        arr[i++] =arr[j];
        while (i<j&& arr[i]<key)
        i++ ;
        if (i<j) 
        arr[j--] = arr[i] ; 
     }
    //递归
    arr[i]=key ;
    quick_sort(arr, left, i-1);
    quick_sort(arr, i+1, right); 
}

}

选择排序

选择排序的基本思想是：每趟排序在待排序列表中选择关键码最小的元素，顺序添加到已将排序好的有序序列中去，直到全部记录都排序完成

简单选择排序

简单选择排序的基本思想是：每趟在待排序的序列中找出最小的记录加到序列头部。直到都排序完成。

void select_sort(int arr[], int len){
for (int i= 0; i<len-1; i++) {
        int temp = i ;
    for (int j=i+1; j<len; j++) {
        if(arr[j]<arr[temp]){
            temp = j ;
        }
    }
    if (temp != i) {
        int arrTemp = arr[i] ;
        arr[i] = arr[temp] ;
        arr[temp] =arrTemp ;
    }
}
}

堆排序

堆排序是对简单选择排序的改进。堆排序利用了前一趟比较的结果，减小了比较的次数，从而提高整个排序的效率。

//调整堆
void Sort::heap_adjust(int arr[], int i, int len){
int child = 2 * i + 1;
int temp;
while (child<len) {
 // 得到子结点中键值较大的结点 这里求的是大根堆, 如果是小根堆，下面变为arr[child + 1] < arr[child]
    if (child < len - 1 && arr[child + 1]>arr[child])
        child ++;
    //这里求的是大根堆，如果求小根堆arr[i] > arr[child]
    if (arr[i] <arr[child])
    {
        temp = arr[i];
        arr[i] = arr[child];
        arr[child] = temp;
        i =child ;
        child = 2 * i + 1;
    }
    else
        break;
}   
}

//堆排序
void Sort::heap_sort(int arr[], int len){
int i;
// 调整序列的前半部分元素，调整完之后第一个元素是序列的最大的元素
for (int i = len / 2 - 1; i >= 0; i--)
{
    heap_adjust(arr, i, len);
}

for (i = len - 1; i > 0; i--)
{
    int temp = arr[0];
    arr[0] = arr[i];
    arr[i] = temp;
    // 不断缩小调整heap的范围，每一次调整完毕保证第一个元素是当前序列的最大值
    heap_adjust(arr, 0, i);
}

}

归并排序

归并排序的基本思想方法是：将两个或者两个以上的有序序列归并成一个有序序列

void merge(int arr[], int temp_arr[], int start_index, int mid_index, int end_index){
int i=start_index;
int k=0;
int j=mid_index+1 ;

//直到一个组数被遍历完
while (i<mid_index+1 && j<1+end_index) {
    if (arr[i]>arr[j]) {
        temp_arr[k++] =arr[j++];
    }else{
        temp_arr[k++] =arr[i++];
    }
}
//将没被遍历完的数组添加到数组中去
while (i<1+mid_index) {
    temp_arr[k++]= arr[i++];
}

while (j<1+end_index) {
    temp_arr[k++] =arr[j++];
}

for (i = 0, j = start_index; j <1+end_index; i ++, j ++)
     arr[j] = temp_arr[i];
}

void merge_sort(int arr[], int arr_temp[],int start_index, int end_index){
if (start_index<end_index) {
    int mid = (start_index+end_index)/2 ;
    merge_sort(arr, arr_temp, start_index, mid);
    merge_sort(arr, arr_temp, mid+1, end_index);
    merge(arr, arr_temp, start_index, mid, end_index);
}

排序的比较

排序方法 | 平均复杂度 | 空间复杂度 | 稳定性
------------ | ------------- | ------------
直接插入排序 | O(n²)| O(1) | 稳定
希尔排序 | O(nlog₂n) | O(1) |不稳定
冒泡排序 | O(n²)|O(1)|稳定
快速排序 | O(nlog₂n) | O(nlog₂n)|不稳定
简单选择排序 | O(n²) | O(1)| 稳定
堆排序 | O(nlog₂n) | O(1)| 不稳定
归并排序 | O(nlog₂n) | O(n)| 稳定

STL中相关排序算法

所有STL sort算法函数的名字列表:

函数名	功能描述
sort	对给定区间所有元素进行排序
stable_sort	对给定区间所有元素进行稳定排序
partial_sort	对给定区间所有元素部分排序
partial_sort_copy	对给定区间复制并排序
nth_element	找出给定区间的某个位置对应的元素
is_sorted	判断一个区间是否已经排好序
partition	使得符合某个条件的元素放在前面
stable_partition	相对稳定的使得符合某个条件的元素放在前面

比较函数：

当你需要按照某种特定方式进行排序时，你需要给sort指定比较函数，否则程序会自动提供给你一个比较函数

vector < int > vect;

sort(vect.begin(), vect.end());//此时相当于调用

sort(vect.begin(), vect.end(), less<int>() );

sort 中的其他比较函数

equal_to	相等
not_equal_to	不相等
less	小于
greater	大于
less_equal	小于等于
greater_equal	大于等于

上述例子中系统自己为sort提供了less仿函数。在STL中还提供了其他仿函数，以下是仿函数列表: 不能直接写入仿函数的名字，而是要写其重载的()函数： less<int>();
当你的容器中元素时一些标准类型（int float char)或者string时，你可以直接使用这些函数模板。但如果你时自己定义的类型或者你需要按照其他方式排序，你可以有两种方法来达到效果：一种是自己写比较函数。另一种是重载类型的'<'操作赋。

全排序：

全排序即把所给定范围所有的元素按照大小关系顺序排列。sort采用的是成熟的"快速排序算法"(目前大部分STL版本已经不是采用简单的快速排序，而是结合内插排序算法)。复杂度为nlog₂n。stable_sort采用的是"归并排序"，分派足够内存时，其算法复杂度为nlog₂n, 否则其复杂度为nlog₂n*log₂n，其优点是会保持相等元素之间的相对位置在排序前后保持一致。

用于全排序的函数有：

void sort(RandomAccessIterator first, RandomAccessIterator last);
void sort(RandomAccessIterator first, RandomAccessIterator last,StrictWeakOrdering comp);
void stable_sort(RandomAccessIterator first, RandomAccessIterator last);
void stable_sort(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp);

局部排序：

partial_sort采用的堆排序（heapsort），它在任何情况下的复杂度都是nlog₂n。

局部排序其实是为了减少不必要的操作而提供的排序方式。

其函数原型为：

void partial_sort(RandomAccessIterator first, RandomAccessIterator middle,RandomAccessIterator last);
void partial_sort(RandomAccessIterator first,RandomAccessIterator middle,RandomAccessIterator last, StrictWeakOrdering comp);
RandomAccessIterator partial_sort_copy(InputIterator first, InputIteratorlast,RandomAccessIteratorresult_first,RandomAccessIterator result_last);
RandomAccessIterator partial_sort_copy(InputIterator first, InputIteratorlast,RandomAccessIteratorresult_first,RandomAccessIterator result_last, Compare comp);

例如：班上有1000个学生，我想知道分数最低的5名是哪些人。
partial_sort(vect.begin(),vect.begin()+5,vect.end(),less<student>());

nth_element 指定元素排序

void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,RandomAccessIterator last,StrictWeakOrdering comp);

例如：班上有1000个学生，我想知道分数排在倒数第4名的学生。
nth_element(vect.begin(), vect.begin()+3, vect.end(),less<student>());

partition 和stable_partition

partition就是把一个区间中的元素按照某个条件分成两类，并没有排序。