训练题：数组排序
训练题：topK
- 场景一：找出topK个最小数
  - 方法一：分治法
  - 方法二：最大值堆
- 场景二：找出第topK大的数
  - 方法一：分治法
  - 方法二：堆
训练题：链表排序
- 递归版
- 迭代版
训练题：排序链表
- 插入排序

训练题：数组排序

方法一：冒泡排序

时间复杂度
- 平均O(n2)
- 最好O(n2)
- 最差O(n2)
- 时间复杂度完全不受数据初始顺序的影响，比如初始已经是有序的，依然要O(n2)，这非常糟糕。
空间复杂度：O(1)
稳定性：稳定 ```cpp

vector MySort( vector &arr ) { if( arr.size() < 2 ) { return arr; }

const auto size = arr.size();
for( int i = 0; i < size - 1; i++ )
{
    for( int j = 0; j < size - 1 - i; j++ )
    {
        if( arr[j] > arr[j + 1] ) { std::swap(arr[j], arr[j + 1]); }
    }
}
return arr;

}

[基本内排序算法](https://www.yuque.com/tvvhealth/cs/vr8mgw?inner=zSQrw&view=doc_embed)
<a name="rLj9b"></a>
## 方法二：插入排序
- 时间复杂度
   - 平均：O(n2)
   - 最好：O(n)，初始序列已经有序。因此小规模排序，插入排序最合适。
   - 最差：O(n2)
- 空间复杂度：O(1)
- 稳定性：稳定
```cpp
vector<int> MySort( vector<int> &arr )
{
    if( arr.size() < 2 ) { return arr; }
    const auto size = arr.size();
    for( int i = 1; i < size; i++ )
    {
        for( int j = i; j < size && arr[j] < arr[j - 1]; j-- )
        {
            std::swap(arr[j], arr[j - 1]);
        }
    }
    return arr;
}

基本内排序算法

方法三：选择排序

时间复杂度
- 平均O(n2)
- 最好O(n2)
- 最差O(n2)
空间复杂度：O(1)
稳定性：不稳定 ```cpp

vector MySort( vector &arr ) { if( arr.size() < 2 ) { return arr; }

const auto size = arr.size();
int tmpIdx = -1;
for( int i = 0; i < size - 1; i++ )
{
    tmpIdx = i;
    for( int j = i + 1; j < size; j++ )
    {
        if( arr[j] < arr[tmpIdx] ) { tmpIdx = j; }
    }
    if( tmpIdx != i ) { std::swap(arr[i], arr[tmpIdx]); }
}
return arr;

}

[基本内排序算法](https://www.yuque.com/tvvhealth/cs/vr8mgw?inner=qglHw&view=doc_embed)
<a name="ywzS4"></a>
## 方法四：希尔排序
- 时间复杂度
   - 平均O(n2)
   - 最差约O(n2)
- 空间复杂度：O(1)
- 稳定性：不稳定
```cpp
vector<int> MySort( vector<int> &arr )
{
    if( arr.size() < 2 ) { return arr; }
    const auto size = arr.size();
    for( int diff = size / 2; diff >= 1; diff /= 2 )
    {
        for( int start = 0; start < diff; start++ ) { _MySort( arr, start, diff ); }
    }
    return arr;
}
void _MySort( vector<int> &arr, const int &start, const int &diff )
{
    const auto size = arr.size();
    for( int i = start + diff; i < size; i += diff )
    {
        for( int j = i; j > start && arr[j] < arr[j - diff]; j -= diff )
        {
            std::swap(arr[j], arr[j - diff]);
        }
    }
}

基本内排序算法

方法五：归并排序


vector<int> MySort( vector<int> &arr )
{
    if( arr.size() < 2 ) { return arr; }
    vector<int> copyArr;
    copyArr.reserve( arr.size() );
    _MySort( arr, copyArr, 0, arr.size() - 1 );
    return arr;
}
void _MySort( vector<int> &arr, vector<int> &copyArr, const int &start, const int &end )
{
    if( end <= start ) { return; }
    //此处可优化：if( ( end - start ) <= 100 ) 执行插入排序
    const int mid = ( start + end ) >> 1;
    _MySort( arr, copyArr, start, mid );
    _MySort( arr, copyArr, mid + 1, end );
    for( int i = start; i <= mid; i++ ) { copyArr[i] = arr[i]; }
    for( int i = end; i >= mid + 1; i-- ) { copyArr[mid + end + 1 - i] = arr[i]; }
    for( int tmpStart = start, tmpLeft = start, tmpRight = end; tmpStart <= end; tmpStart++ )
    {
        if( copyArr[tmpLeft] < copyArr[tmpRight] ) { arr[tmpStart] = copyArr[tmpLeft++]; }
        else { arr[tmpStart] = copyArr[tmpRight--]; }
    }
}

基本内排序算法

方法六：快速排序


vector<int> MySort( vector<int> &arr )
{
    if( arr.size() < 2 ) { return arr; }
    _MySort( arr, 0, arr.size() - 1 );
    return arr;
}
void _MySort( vector<int> &arr, const int &start, const int &end )
{
    if( end <= start ) { return; }
    // 此处可优化：if( ( end - start ) <= 100 ) 执行插入排序
    const int pivot = ( start + end ) >> 1;
    if( pivot != end ) { std::swap(arr[pivot], arr[end]); }
    int k = partition( arr, start - 1, end, arr[end] );
    if( k != end ) { std::swap(arr[k], arr[end]); }
    _MySort( arr, start, k - 1 );
    _MySort( arr, k + 1, end );
}
int partition( vector<int> &arr, int start, int end, const int &pivotVal )
{
    while( true )
    {
        while( ++start != end && arr[start] < pivotVal );
        while( --end != start && !( arr[end] < pivotVal ) );
        if( start < end ) { std::swap(arr[start], arr[end]); }
        else { break; }
    }
    return start;
}

基本内排序算法

方法七：堆排序


vector<int> MySort( vector<int> &arr )
{
    if( arr.size() < 2 ) { return arr; }
    Heap heap( arr );
    while( !heap.empty() ) { heap.pop(); }
    return arr;
}
class Heap
{
    public:
    Heap( vector<int> &arr );
    void pop();
    bool empty();
    private:
    void siftDown( const int & );
    int leftChild( const int & );
    int rightChild( const int & );
    bool leaf( const int & );
    private:
    vector<int> &_data;
    int _dataSize;
};
Heap::Heap( vector<int> &arr )
    : _data( arr )
    , _dataSize( arr.size() )
{
    for( int i = ( arr.size() >> 1 ) - 1; i >= 0; i-- ) { siftDown( i ); }
}
void Heap::pop()
{
    if( _dataSize )
    {
        std::swap( _data[0], _data[_dataSize - 1] );
        _dataSize--;
        siftDown( 0 );
    }
}
bool Heap::empty() return _dataSize == 0;
void Heap::siftDown( const int &index )
{
    if( !leaf( index ) )
    {
        int maxChild = leftChild( index );
        int rightchild = rightChild( index );
        if( rightchild < _dataSize && _data[maxChild] < _data[rightchild] )
        {
            maxChild = rightchild;
        }
        if( _data[index] < _data[maxChild] )
        {
            std::swap( _data[maxChild], _data[index] );
            siftDown( maxChild );
        }
    }
}
int Heap::leftChild( const int &index ) return ( index << 1 ) + 1;
int Heap::rightChild( const int &index ) return ( index << 1 ) + 2;
bool Heap::leaf( const int &index ) return index > ( ( _dataSize >> 1 ) - 1 );

基本内排序算法

训练题：topK

场景一：找出topK个最小数

题目：http://t.cn/A6V7bQke

方法一：分治法

快速排序的partition方法。


vector<int> getLeastNumbers(vector<int>& arr, int k) {
    if(arr.empty() || k > arr.size()) return {};
    if(arr.size() == k) return arr;
    const auto size = arr.size();
    short start = 0, end = size - 1, tmp = k;
    while(true) {
        // 快排分区
        std::swap(arr[start + ((end - start)>>1)], arr[end]);
        int pivot = paritition(arr, start-1, end, arr[end] );
        std::swap(arr[pivot], arr[end]);
        if(pivot == k) break;    // 左分区+pivot刚好=k个。
        else if(pivot < k) {    // 第k小的数在pivot的右侧，
            // 那么问题改成在[pivot+1, end]区间查找k-左区间[start, pivot]个数，因为区间[start, pivot]肯定是最小的一批数
            start = pivot + 1;
            tmp  = tmp - (pivot - start + 1);
        }
        else end = pivot - 1;   //第k小的数在pivot左侧，那么问题改成在start, pivot-1的区间寻找第k小的数
    }
    return vector<int>(arr.begin(), arr.begin()+k);
}
// 快排的partition
short paritition(vector<int> &arr, short start, short end, int pivotVal){
    while(true){
        while(++start < end && arr[start] < pivotVal);
        while(--end > start && !(arr[end] < pivotVal));
        if(start < end) std::swap(arr[start], arr[end]);
        else break;
    }
    return start;
}

方法二：最大值堆

用数列的前K个值构建一个最大值堆，然后将剩余的值挨个与堆顶的值比较，合适则替换堆顶，然后siftdown到合适位置。


class Heap
{
public:
    Heap( vector<int> &arr ) : _data( arr ), _dataSize( arr.size() )
    {
        for( int i = ( arr.size() >> 1 ) - 1; i >= 0; i-- ) { siftDown( i ); }
    }
    bool empty() {return _dataSize == 0;}
    int top( ) {return _data[0];}
    void setTop( const int &val )
    {
        if( _data[0] != val )
        {
            _data[0] = val;
            siftDown( 0 );
        }
    }
private:
    int leftChild( const int &index ) { return ( index << 1 ) + 1; }
    int rightChild( const int &index ) { return ( index << 1 ) + 2; }
    bool leaf( const int &index ) { return index > ( ( _dataSize >> 1 ) - 1 ); }
    void siftDown( const int &index )
    {
        if( !leaf( index ) )
        {
            int maxChild = leftChild( index );
            int rightchild = rightChild( index );
            if( rightchild < _dataSize && _data[maxChild] < _data[rightchild] )
            {
                maxChild = rightchild;
            }
            if( _data[index] < _data[maxChild] )
            {
                std::swap( _data[maxChild], _data[index] );
                siftDown( maxChild );
            }
        }
    }
public:
    vector<int> &_data;
    int _dataSize;
};
vector<int> GetLeastNumbers_Solution( vector<int> input, int k )
{
    if( k > input.size() || k <= 0 || input.empty() ) return{};
    if( k == static_cast<int>( input.size() ) ) { return input; }
    vector<int> container{ input.begin(), input.begin() + k };
    Heap heap( container );
    for( auto it = input.begin() + k; it != input.end(); it++ ) if( *it < heap.top() ) { heap.setTop( *it ); }
    return heap._data;
};

场景二：找出第topK大的数

题目：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/

方法一：分治法


int findKth( vector<int> input, int n, int k )
{
    if( k > n || k <= 0 || input.empty() || input.size() != n ) { return INT_MAX; }
    // 找第K大的数等于找第n-k+1小的数
    k = n - k + 1;
    int pivot   = -1;
    int rankIdx = -1;
    int left    = 0;
    int right   = n - 1;
    while( true )
    {
        pivot = ( left + right ) >> 1;
        if( pivot != right ) { std::swap( input[pivot], input[right] ); }
        rankIdx = partition( input, left - 1, right, input[right] );
        if( rankIdx != right ) { std::swap( input[rankIdx], input[right] ); }
        if( ( rankIdx + 1 ) == k ) { return input[rankIdx]; }
        else if( ( rankIdx + 1 ) < k ) { left = rankIdx + 1; }
        else { right = rankIdx - 1; }
    }
}
// 对[start+1, end]区间的数目进行分区，其中end位置的值是pivotVal
// 设返回值是k，表示位置。则有[0, ..., k-1] < [k] < [k+1, ...]
int partition( vector<int> &input, int start, int end, int pivotVal )
{
    while( true )
    {
        while( ++start != end && input[start] < pivotVal );
        while( --end != start && !( input[end] < pivotVal ) );
        if( start < end ) { std::swap( input[start], input[end] ); }
        else { break; }
    }
    return start;
}

方法二：堆

用数列的前K个值构建一个最小值堆，然后将剩余的值挨个与堆顶的值比较，合适则替换堆顶，然后siftdown到合适位置。


int findKthLargest(vector<int>& nums, int k) {
    if(nums.size() == 1) return nums[0];
    const auto size = nums.size();
    int idx = 0;
    priority_queue<int, vector<int>, greater<int>> q;
    // 填满k个元素。
    for(idx = 0; idx < k; q.push(nums[idx]), ++idx);
    // 筛选出K个最大的元素
    for(; idx < size; ++idx) {
        if(q.top() < nums[idx]){
            q.pop();
            q.push(nums[idx]);
        }
    }
    // 堆顶就是第K大的元素
    return q.top();
}

训练题：链表排序

题目：https://leetcode-cn.com/problems/insertion-sort-list/

递归版


ListNode* insertionSortList(ListNode* head) {
    if(!head || !head->next) return head;
    ListNode tmpHead, *next = head->next;
    tmpHead.next = head;
    head->next = nullptr;
    return insertSort(&tmpHead, next);
}
ListNode* insertSort(ListNode* head, ListNode* nodeToInsert)
{
    if(!nodeToInsert) return head->next;
    ListNode* nextToInsert = nodeToInsert->next;
    ListNode* tmpNode = head;
    for(; tmpNode->next && tmpNode->next->val <= nodeToInsert->val; tmpNode = tmpNode->next);
    ListNode* fuck = tmpNode->next;
    tmpNode->next = nodeToInsert;
    nodeToInsert->next = fuck;
    return insertSort(head, nextToInsert);
}

迭代版


ListNode* insertionSortList(ListNode* head) {
    if(!head || !head->next) return head;
    ListNode tmpHead;
    tmpHead.next = head;
    ListNode *next = head->next;
    head->next = nullptr;
    ListNode* tmpNode = nullptr;
    for(ListNode* nodeToAdd = next; nodeToAdd;){
        // 找到最后一个不大于nodeToAdd的节点
        for(tmpNode = &tmpHead; tmpNode->next && tmpNode->next->val <= nodeToAdd->val; tmpNode = tmpNode->next);
        ListNode* nextTmpNode = tmpNode->next;
        ListNode* nextToAdd = nodeToAdd->next;
        tmpNode->next = nodeToAdd;
        nodeToAdd->next = nextTmpNode;
        nodeToAdd = nextToAdd;
    }
    return tmpHead.next;
}

训练题：排序链表

题目：https://leetcode-cn.com/problems/sort-list/

插入排序

时间复杂度：O（n2）
空间复杂度：O（1）


ListNode* sortList(ListNode* head) {
    if(!head || !head->next) return head;
    // tmpHead：临时表头，后面连接的是已排序的链表
    ListNode tmpHead, *next = head->next;
    // 初始情况，tmpHead后面是一个head链表头节点。
    tmpHead.next = head;
    head->next = nullptr;
       // 每次次循环将剩余链表的表头nodeToAdd插入到tmpHead链表的合适位置中。
    for(ListNode* nodeToAdd = next, *afterNode; nodeToAdd;){
        // afterNode要么是tmpHead链表的末尾，要么是最后一个不大于nodeToAdd的节点
        for(afterNode = &tmpHead; afterNode->next && afterNode->next->val <= nodeToAdd->val; afterNode = afterNode->next);
        // 将nodeToAdd插入到afterNode的后面
        ListNode* next_afterNode = afterNode->next;
        ListNode* next_nodeToAdd = nodeToAdd->next;
        afterNode->next = nodeToAdd;
        nodeToAdd->next = next_afterNode;
        nodeToAdd = next_nodeToAdd;
    }
    return tmpHead.next;
}

计算机科学

算法训练_内排序

训练题：数组排序

方法一：冒泡排序

方法三：选择排序

方法五：归并排序

方法六：快速排序

方法七：堆排序

训练题：topK

场景一：找出topK个最小数

方法一：分治法

方法二：最大值堆

场景二：找出第topK大的数

方法一：分治法

方法二：堆

训练题：链表排序

递归版

迭代版

训练题：排序链表

插入排序