美文网首页iOSer 的自我修养Android面试宝典首页投稿（暂停使用，暂停投稿）
程序员面试之算法备忘录（五） | 排序

程序员面试之算法备忘录（五） | 排序

作者: rh_Jameson | 来源:发表于2016-06-20 20:13 被阅读533次

    前言

    本文是题主准备面试时记录下的笔记整理而来，稍显粗陋，还请各位撸友勿喷哈！

    Topic

    • 目录

    • 目标

      • 熟练使用常用数据结构的基本操作
      • 加深对常用算法与技巧的理解
      • 面试

    • 参考

      • 《程序员面试金典》
      • 《剑指offer》
      • Leetcode
      • 《结构之法 --July》

    排序篇

    1_1.BubbleSort

        //冒泡排序
    static void BubbleSort(vector<int> &v){
        int len = v.size(), flag;       //数组长度 & 交换标记变量
        for(int i = 0; i < len; ++i){
            flag = 0;                   //初始化标记为0
            for(int j = 1; j < len - i; ++j){
                if(v[j - 1] > v[j]){
                    swap(v[j - 1],v[j]);
                    flag = 1;           //发生交换，标记变量置1    
                }
            }
            if(flag == 0)   //一轮比较后，如未发生交换，说明已排好序
                break;
        }
    }

    1_2.SelectSort

        //选择排序
    static void SelectSort(vector<int> &v){
        int len = v.size(), min_idx;    //数组长度 & 无序区最小元素位置
        for(int i = 0; i < len; ++i){   //i：无序区中开头位置
            min_idx = i;
            //寻找无序区中最小元素的位置
            for(int j = i + 1; j < len; ++j){   
                if(v[min_idx] > v[j])
                    min_idx = j;
            }
            //最小元素位置如不等于i，则交换位置
            if(min_idx != i){
                swap(v[min_idx], v[i]);
            }
        }
    }

    1_3.InsertSort

        //插入排序
    static void InsertSort(vector<int> &v){
        int len = v.size(), tmp, i, j;
        for(i = 1; i < len; ++i){
            tmp = v[i];
            for(j = i; j > 0 && tmp < v[j - 1]; --j)
                v[j] = v[j - 1];
            v[j] = tmp;
        }  
    }

    1_4.ShellSortSh

        //希尔排序(希尔增量)
    static void ShellSortSh(vector<int> &v){
        int len = v.size();
        int gap, i, j, tmp;
        /* 形式一 */
        for(gap = len / 2; gap > 0; gap /= 2){
            //里面两层循环是实现插排的代码
            for(i = gap; i < len; ++i){
                tmp = v[i];
                for(j = i; j >= gap && tmp < v[j - gap]; j -= gap)
                    v[j] = v[j - gap];
                v[j] = tmp;
            }
        }
        
        /* 形式二: 
        //初始化最大步长
        for(gap = 1; gap <= (len - 1) / 4; gap = 2 * gap);      //普林斯顿大学给出的写法
        for(; gap > 0; gap /= 2){
            for(i = gap; i < len; ++i){
                tmp = v[i];
                for(j = i; j >= gap && tmp < v[j - gap]; j -= gap)
                    v[j] = v[j - gap];
                v[j] = tmp;
            }
        }
        */      
    }

    1_5.ShellSortKn

        //希尔排序(Knuth增量)
    static void ShellSortKn(vector<int> &v){
        int len = v.size();
        int gap, i, j, tmp;
        //初始化最大步长
        //for(gap = 1; gap <= (len - 1) / 9; gap = 3 * gap + 1);    //普林斯顿大学给出的写法
        for(gap = 1; gap < len / 3; gap = 3 * gap + 1);
        
        for(; gap > 0; gap /= 3){
            for(i = gap; i < len; ++i){
                tmp = v[i];
                for(j = i; j >= gap && tmp < v[j - gap]; j -= gap)
                    v[j] = v[j - gap];
                v[j] = tmp;
            }
        }
    }

    1_6.MergeSortUp2Down
    1_7.MergeSortDown2Up

        //归并排序外部接口
    static void IMergeSort(vector<int> &v){
        int len = v.size();
        MergeSortUpToDown(v, 0, len - 1);
        //MergeSortDownToUp(v, len);
        
    }
    //自顶向下归并排序实现
    static void MergeSortUpToDown(vector<int> &v, int start, int end){
        if(start < end){
            int mid = (start + end) / 2;
            //递归分解
            MergeSortUpToDown(v, start, mid);
            MergeSortUpToDown(v, mid + 1, end);
            //合并
            Merge(v, start, mid, end);
        }
    }
    //归并实现关键代码
    static void Merge(vector<int> &v, int start, int mid, int end){
        //初始化临时数组
        vector<int> tmp( v.size() );
        //初始化位置坐标
        int leftPos = start, leftEnd = mid;
        int rightPos = mid + 1, rightEnd = end;
        int tmpPos = leftPos;
        int numElement = end - start + 1;
        //归并主实现
        while(leftPos <= leftEnd && rightPos <= rightEnd){
            if(v[leftPos] <= v[rightPos])
                tmp[tmpPos++] = v[leftPos++];
            else
                tmp[tmpPos++] = v[rightPos++];
        }
        //拷贝左半段剩余的的元素
        while(leftPos <= leftEnd)
            tmp[tmpPos++] = v[leftPos++];
        //拷贝右半段剩余的元素
        while(rightPos <= rightEnd)
            tmp[tmpPos++] = v[rightPos++];
        //拷贝回原数组
        //for(int i = rightEnd; i >= start; --rightEnd){
        for(int i = 0; i < numElement; ++i, --rightEnd){
            v[rightEnd] = tmp[rightEnd];
        }
    }

    //自底向上归并排序实现
    static void MergeSortDownToUp(vector<int> &v, int len){
        /* 拆分版：遍历实现相邻两组的元素进行归并排序
        for(int gap = 1; gap < len; gap *= 2){
            mergeGroups(v, len, gap);
        }
        */
        /* 合并版 */
        int i;
        //遍历实现相邻两组的元素进行归并排序
        for(int gap = 1; gap < len; gap *= 2){
            //相邻的子数组归并排序的主实现
            for(i = 0; i + 2 * gap - 1 < len; i += (2 * gap) ){
                Merge(v, i, i + gap - 1, i + 2 * gap - 1);
            }
            //组数为奇数时，剩余一个组未配对
            if(i + gap - 1 < len){
                Merge(v, i, i + gap - 1, len - 1);
            }
        }
    }
    //分组合并排序实现（将相邻的子数组进行合并排序）
    static void mergeGroups(vector<int> &v, int len, int gap){
        int i;
        //相邻的子数组归并排序的主实现
        for(i = 0; i + 2 * gap - 1 < len; i += (2 * gap) ){
            Merge(v, i, i + gap - 1, i + 2 * gap - 1);
        }
        //组数为奇数时，剩余一个组未配对
        if(i + gap - 1 < len){
            Merge(v, i, i + gap - 1, len - 1);
        }
    }

    1_8.HeapSort

        //堆排序
    static void HeapSort(vector<int> &v){
        int len = v.size();
        //建立初始堆
        for(int i = len / 2; i >= 0; --i){
            percDown(v, i, len);
        }
        //deleteMax
        for(int j = len - 1; j > 0; --j){
            swap(v[0], v[j]);
            percDown(v, 0, j);
        }
    }
    //堆排序下滤实现
    static void percDown(vector<int> &v, int iter, int len){
        int child;
        int tmp = v[iter];      //create hole
        for( ; 2 * iter + 1 < len; iter = child){
            child = 2 * iter + 1;       //获取该节点的左孩子下标
            //如有右孩子，且右孩子大于左孩子，下标改成右孩子下标
            if(child != len - 1 && v[child] < v[child + 1] )
                child++;
            //孩子结点值大于该结点值，则下滤
            if(tmp < v[child])
                v[iter] = v[child];
            else    //否则，说明结点处于正确位置，可跳出循环
                break;
        }
        v[iter] = tmp;          //把hole堵上
    }

    1_9.QuickSort

        //快速排序
    static void QuickSort(vector<int> &v){
        QuickSortRecursion(v, 0, v.size() - 1);
    }
    static void QuickSortRecursion(vector<int> &v, int left, int right){
        /* 优化做法 */
        if(left + 5 <= right){
            int pivot = getPivot(v, left, right);
            int front = left;
            int rear = right - 1;
            //int front = left + 1;
            //int rear = right - 2;
            while(1){
                while(v[++front] < pivot){ }
                while(v[--rear] > pivot){ }
                if(front < rear)
                    swap(v[front], v[rear]);
                else
                    break;
            }
            swap(v[front], v[right - 1]);
            QuickSortRecursion(v, left, front - 1);     //sort small elements
            QuickSortRecursion(v, front + 1, right);    //sort large elements
        }
        else{
            InsertSortForQSort(v, left, right);
        }
        
        /* 纯快排做法 
        if(right - left <= 1){                      //递归出口，小于两个元素情况的处理
            if(v[left] > v[right])
                swap(v[left],v[right]);
            return;
        }
        int pivot = getPivot(v, left, right);       //枢纽元
        int front = left;
        int rear = right - 1;
        while(1){
            //首尾指针向中间靠拢
            while(v[++front] < pivot){ }            
            while(v[--rear] > pivot){ }
            //front小于rear则交换元素
            if(front < rear)
                swap(v[front], v[rear]);
            else
                break;      //front、rear交错，则不再交换，跳出循环
        }
        swap(v[front], v[right - 1]);   //将枢纽元放到正确位置
        QuickSortRecursion(v, left, front - 1);     //sort small elements
        QuickSortRecursion(v, front + 1, right);    //sort large elements
        */
    }   
    //三数中值取枢纽元
    static int getPivot(vector<int> &v, int left, int right){
        int mid = (left + right) / 2;
        if(v[left] > v[mid])
            swap(v[left], v[mid]);
        if(v[left] > v[right])
            swap(v[left],v[right]);
        if(v[mid] > v[right])
            swap(v[mid], v[right]);
        swap(v[mid], v[right - 1]);
        return v[right - 1];
    }
    
    //适配快排的插入排序
    static void InsertSortForQSort(vector<int> &v,int left, int right){
        int tmp, i, j;
        for(i = left + 1; i <= right; ++i){
            tmp = v[i];
            for(j = i; j >= left && tmp < v[j - 1]; --j)
                v[j] = v[j - 1];
            v[j] = tmp;
        }
        
    }

    类代码

    /*************************************************************************
    > File Name:        sort.h
    > Description:      
                        （1）实现常用的各种排序
                        （2）利用回调函数实现
    > Conclusion:          
    > Author:           rh_Jameson
    > Created Time:     2015年03月06日 星期五 20时33分45秒
 ************************************************************************/

#ifndef _SORT_H
#define _SORT_H

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;

//字符串数组，通过该数组适配switch
static string sort_type[] = {"BubbleSort", "SelectSort", "InsertSort",
                            "ShellSortSh", "ShellSortKn", "IMergeSort", 
                             "HeapSort","QuickSort"
                            };
class Sort {
public:
    //Sort构造函数
    Sort(vector<int> &v, string sort_name){
        if(v.empty()){
            cout << "数组为空" << endl;
            return;
        }
        int len = 8, i;
        //判断要采取何种排序
        for(i = 0; i < len; ++i){
            if(sort_name == sort_type[i]){
                break;
            }
        }
        switch(i){
            case 0:     CallSort = BubbleSort;  break;
            case 1:     CallSort = SelectSort;  break;
            case 2:     CallSort = InsertSort;  break;
            case 3:     CallSort = ShellSortSh; break;
            case 4:     CallSort = ShellSortKn; break;
            case 5:     CallSort = IMergeSort;  break;
            case 6:     CallSort = HeapSort;    break;
            case 7:     CallSort = QuickSort;   break;
            default:    cout << "无此排序！" << endl;   return;
        }
        CallSort(v);
    }
    //两数交换函数
    static void swap(int &num1, int &num2){
        int tmp = num1;
        num1 = num2;
        num2 = tmp;
    }
    //冒泡排序
    static void BubbleSort(vector<int> &v){
        int len = v.size(), flag;       //数组长度 & 交换标记变量
        for(int i = 0; i < len; ++i){
            flag = 0;                   //初始化标记为0
            for(int j = 1; j < len - i; ++j){
                if(v[j - 1] > v[j]){
                    swap(v[j - 1],v[j]);
                    flag = 1;           //发生交换，标记变量置1    
                }
            }
            if(flag == 0)   //一轮比较后，如未发生交换，说明已排好序
                break;
        }
    }
    //选择排序
    static void SelectSort(vector<int> &v){
        int len = v.size(), min_idx;    //数组长度 & 无序区最小元素位置
        for(int i = 0; i < len; ++i){   //i：无序区中开头位置
            min_idx = i;
            //寻找无序区中最小元素的位置
            for(int j = i + 1; j < len; ++j){   
                if(v[min_idx] > v[j])
                    min_idx = j;
            }
            //最小元素位置如不等于i，则交换位置
            if(min_idx != i){
                swap(v[min_idx], v[i]);
            }
        }
    }
    //插入排序
    static void InsertSort(vector<int> &v){
        int len = v.size(), tmp, i, j;
        for(i = 1; i < len; ++i){
            tmp = v[i];
            for(j = i; j > 0 && tmp < v[j - 1]; --j)
                v[j] = v[j - 1];
            v[j] = tmp;
        }
        
    }    
    //希尔排序(希尔增量)
    static void ShellSortSh(vector<int> &v){
        int len = v.size();
        int gap, i, j, tmp;
        /* 形式一 */
        for(gap = len / 2; gap > 0; gap /= 2){
            //里面两层循环是实现插排的代码
            for(i = gap; i < len; ++i){
                tmp = v[i];
                for(j = i; j >= gap && tmp < v[j - gap]; j -= gap)
                    v[j] = v[j - gap];
                v[j] = tmp;
            }
        }
        
        /* 形式二: 
        //初始化最大步长
        for(gap = 1; gap <= (len - 1) / 4; gap = 2 * gap);      //普林斯顿大学给出的写法
        for(; gap > 0; gap /= 2){
            for(i = gap; i < len; ++i){
                tmp = v[i];
                for(j = i; j >= gap && tmp < v[j - gap]; j -= gap)
                    v[j] = v[j - gap];
                v[j] = tmp;
            }
        }
        */      
    }
    //希尔排序(Knuth增量)
    static void ShellSortKn(vector<int> &v){
        int len = v.size();
        int gap, i, j, tmp;
        //初始化最大步长
        //for(gap = 1; gap <= (len - 1) / 9; gap = 3 * gap + 1);    //普林斯顿大学给出的写法
        for(gap = 1; gap < len / 3; gap = 3 * gap + 1);
        
        for(; gap > 0; gap /= 3){
            for(i = gap; i < len; ++i){
                tmp = v[i];
                for(j = i; j >= gap && tmp < v[j - gap]; j -= gap)
                    v[j] = v[j - gap];
                v[j] = tmp;
            }
        }
    }
    //归并排序外部接口
    static void IMergeSort(vector<int> &v){
        int len = v.size();
        MergeSortUpToDown(v, 0, len - 1);
        //MergeSortDownToUp(v, len);
        
    }
    //自顶向下归并排序实现
    static void MergeSortUpToDown(vector<int> &v, int start, int end){
        if(start < end){
            int mid = (start + end) / 2;
            //递归分解
            MergeSortUpToDown(v, start, mid);
            MergeSortUpToDown(v, mid + 1, end);
            //合并
            Merge(v, start, mid, end);
        }
    }
    //归并实现关键代码
    static void Merge(vector<int> &v, int start, int mid, int end){
        //初始化临时数组
        vector<int> tmp( v.size() );
        //初始化位置坐标
        int leftPos = start, leftEnd = mid;
        int rightPos = mid + 1, rightEnd = end;
        int tmpPos = leftPos;
        int numElement = end - start + 1;
        //归并主实现
        while(leftPos <= leftEnd && rightPos <= rightEnd){
            if(v[leftPos] <= v[rightPos])
                tmp[tmpPos++] = v[leftPos++];
            else
                tmp[tmpPos++] = v[rightPos++];
        }
        //拷贝左半段剩余的的元素
        while(leftPos <= leftEnd)
            tmp[tmpPos++] = v[leftPos++];
        //拷贝右半段剩余的元素
        while(rightPos <= rightEnd)
            tmp[tmpPos++] = v[rightPos++];
        //拷贝回原数组
        //for(int i = rightEnd; i >= start; --rightEnd){
        for(int i = 0; i < numElement; ++i, --rightEnd){
            v[rightEnd] = tmp[rightEnd];
        }
    }

    //自底向上归并排序实现
    static void MergeSortDownToUp(vector<int> &v, int len){
        /* 拆分版：遍历实现相邻两组的元素进行归并排序
        for(int gap = 1; gap < len; gap *= 2){
            mergeGroups(v, len, gap);
        }
        */
        /* 合并版 */
        int i;
        //遍历实现相邻两组的元素进行归并排序
        for(int gap = 1; gap < len; gap *= 2){
            //相邻的子数组归并排序的主实现
            for(i = 0; i + 2 * gap - 1 < len; i += (2 * gap) ){
                Merge(v, i, i + gap - 1, i + 2 * gap - 1);
            }
            //组数为奇数时，剩余一个组未配对
            if(i + gap - 1 < len){
                Merge(v, i, i + gap - 1, len - 1);
            }
        }
    }
    //分组合并排序实现（将相邻的子数组进行合并排序）
    static void mergeGroups(vector<int> &v, int len, int gap){
        int i;
        //相邻的子数组归并排序的主实现
        for(i = 0; i + 2 * gap - 1 < len; i += (2 * gap) ){
            Merge(v, i, i + gap - 1, i + 2 * gap - 1);
        }
        //组数为奇数时，剩余一个组未配对
        if(i + gap - 1 < len){
            Merge(v, i, i + gap - 1, len - 1);
        }
    }
    
    //堆排序
    static void HeapSort(vector<int> &v){
        int len = v.size();
        //建立初始堆
        for(int i = len / 2; i >= 0; --i){
            percDown(v, i, len);
        }
        //deleteMax
        for(int j = len - 1; j > 0; --j){
            swap(v[0], v[j]);
            percDown(v, 0, j);
        }
    }
    //堆排序下滤实现
    static void percDown(vector<int> &v, int iter, int len){
        int child;
        int tmp = v[iter];      //create hole
        for( ; 2 * iter + 1 < len; iter = child){
            child = 2 * iter + 1;       //获取该节点的左孩子下标
            //如有右孩子，且右孩子大于左孩子，下标改成右孩子下标
            if(child != len - 1 && v[child] < v[child + 1] )
                child++;
            //孩子结点值大于该结点值，则下滤
            if(tmp < v[child])
                v[iter] = v[child];
            else    //否则，说明结点处于正确位置，可跳出循环
                break;
        }
        v[iter] = tmp;          //把hole堵上
    }
    //快速排序
    static void QuickSort(vector<int> &v){
        QuickSortRecursion(v, 0, v.size() - 1);
    }
    static void QuickSortRecursion(vector<int> &v, int left, int right){
        /* 优化做法 */
        if(left + 5 <= right){
            int pivot = getPivot(v, left, right);
            int front = left;
            int rear = right - 1;
            //int front = left + 1;
            //int rear = right - 2;
            while(1){
                while(v[++front] < pivot){ }
                while(v[--rear] > pivot){ }
                if(front < rear)
                    swap(v[front], v[rear]);
                else
                    break;
            }
            swap(v[front], v[right - 1]);
            QuickSortRecursion(v, left, front - 1);     //sort small elements
            QuickSortRecursion(v, front + 1, right);    //sort large elements
        }
        else{
            InsertSortForQSort(v, left, right);
        }
        
        /* 纯快排做法 
        if(right - left <= 1){                      //递归出口，小于两个元素情况的处理
            if(v[left] > v[right])
                swap(v[left],v[right]);
            return;
        }
        int pivot = getPivot(v, left, right);       //枢纽元
        int front = left;
        int rear = right - 1;
        while(1){
            //首尾指针向中间靠拢
            while(v[++front] < pivot){ }            
            while(v[--rear] > pivot){ }
            //front小于rear则交换元素
            if(front < rear)
                swap(v[front], v[rear]);
            else
                break;      //front、rear交错，则不再交换，跳出循环
        }
        swap(v[front], v[right - 1]);   //将枢纽元放到正确位置
        QuickSortRecursion(v, left, front - 1);     //sort small elements
        QuickSortRecursion(v, front + 1, right);    //sort large elements
        */
    }   
    //三数中值取枢纽元
    static int getPivot(vector<int> &v, int left, int right){
        int mid = (left + right) / 2;
        if(v[left] > v[mid])
            swap(v[left], v[mid]);
        if(v[left] > v[right])
            swap(v[left],v[right]);
        if(v[mid] > v[right])
            swap(v[mid], v[right]);
        swap(v[mid], v[right - 1]);
        return v[right - 1];
    }
private:
    void (*CallSort)(vector<int> &v);
    
    //适配快排的插入排序
    static void InsertSortForQSort(vector<int> &v,int left, int right){
        int tmp, i, j;
        for(i = left + 1; i <= right; ++i){
            tmp = v[i];
            for(j = i; j >= left && tmp < v[j - 1]; --j)
                v[j] = v[j - 1];
            v[j] = tmp;
        }
        
    }    
};

#endif

    相关文章

      网友评论

        本文标题：程序员面试之算法备忘录（五） | 排序

        本文链接：https://www.haomeiwen.com/subject/zaakdttx.html

        延伸阅读

        深度阅读

        • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

        栏目导航

        热点阅读

        iOSer 的自我修养

        Android面试宝典

        首页投稿（暂停使用，暂停投稿）

        程序员

        @IT·互联网

        work

        关于我们|服务条款|联系我们|程序员面试之算法备忘录（五） | 排序|投稿指南|网站地图|RSS订阅|排版工具|手机版

        提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

        Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

        备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

        本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

        所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！