基本概念及分类

排序:排序就是将有记录的东西,按照某个关键字进行递增的或递减的排序下来

稳定性:举例说明,这里有一串数组:1 9 7 4 5 5 6,其中有两个5,在进行排序
在这里插入图片描述
内部排序：元素全部放在内存中的排序。

外部排序：元素太多，内存中放不下,排序过程的要求不能在内外存之间移动数据的排序。
在这里插入图片描述

插入排序

直接将一个数插入到有序的数组中,直接形成新的有序数组,相当于我们玩扑克牌,从小到大整理扑克牌,进行插入.

void insertSort(int* arr, int n){ 
    //假设第一个数据是有序的
    //未插入数据[1,n)
    for (int i = 0; i < n; ++i){ 
        //从有序的最后一个位置进行遍历
        int end = i - 1;
        int data = arr[i];
        while (end >= 0 && arr[end] >= data){     //满足条件时
            //较大的数据向后移动
            arr[end + 1] = arr[end];        //数据后移
            --end;        //循环
        }
        arr[end + 1] = data;    //直接插入
    }
}

这个题目,相当于顺序表的头插,大体一致,大家可以具体了解了解点击此处

希尔排序

在这里插入图片描述

void shellSort(int* arr, int n){ 
    int gap = n;        //创建gap值
    //一趟哈希排序
    while (gap > 1){ 
        gap = gap / 3 + 1;    //让其等于一个值进行交换
        for (int i = gap; i < n; ++i){     //循环内部
            //同组数据,最后一个有序数组的位置
            int end = i - gap;
            //待插入的数据
            int data = arr[i];
            while (end >= 0 && arr[end]>data){ 
                arr[end + gap] = arr[end];    
                end -= gap;        //gap逐渐减到1
            }
            arr[end + gap] = data;        //交换
        }
    }
}

选择排序

插入理解动图点击此处跳转看图
在一组元素中,找到最小的放在最前面,然后剩下的进行二次寻找,直到排序完成!

void selectSort(int* arr, int n){ 
    int start = 0;
    int end = n - 1;        //定义尾部节点
    while (start < end){         //循环开始
        //首先找到最小值的位置
        int minIdx = start;        
        int i;
        for (i = start + 1; i <= end; ++i){         //进行遍历
            if (arr[i] < arr[minIdx])        //如果存在最小的
                minIdx=i;    //让它等于i
        }
        //将最小值存在起始位置
        Swap(arr, start, minIdx);        //这里调用了一个最最最简单的交换元素,我就不具体写了,相信大家也会.
        //循环
        ++start;
    }
}

这一个代码,我们是在每一次遍历寻找的时候,同时找到一个最大的和最小的,这样的话,需要遍历的次数就缩减了一半,提高了我们的效率!

void selectSortPlus(int* arr, int n){ 
    int start = 0;
    int end = n - 1;
    //我们运用同样的方法,只不过在每次遍历的时候
    //寻找一个最大的和一个最小的,这样遍历就能减少一半
    while (start < end){ 
        int minIdx = start;        //定义最小
        int maxIdx = start;        //定义最大
        for (int j = start + 1; j <= end; ++j){         //开始遍历
            if (arr[j] < arr[minIdx])        //找到最小的
                minIdx = j;        //赋值
            if (arr[j]>arr[maxIdx])            //找到最大的
                maxIdx = j;        //赋值
        }
        //最小值放在头部
        Swap(arr, start, minIdx);        //交换
        //判断最大值位置是否在起始位置
        if (maxIdx == start)        //如果最大值在起始位置,就说明只存在一个元素,最大最小相等!
            maxIdx = minIdx;
        //最大值放在尾部
        Swap(arr, end, maxIdx);
        ++start;        //循环继续
        --end;
    }
}

堆排序

在这里插入图片描述

void shiftDown(int* arr, int n, int parent){ 
    int child = 2 * parent + 1;        //最后一个孩子节点的位置
    while (child < n){             //循环
        if (child + 1 < n&&arr[child + 1] > arr[child])    //存在则继续
            ++child;
        if (arr[child]>arr[parent]){     //孩子节点大于父节点,则交换
            Swap(arr, child, parent);    //交换,如同图中的橙色线
            parent = child;        //更新
            child = 2 * parent + 1;    //更新孩子节点
        }
        else
            break;        //不满足直接结束
    }
}
void heapSort(int* arr, int n){ 
    for (int i = (n - 2) / 2; i >= 0; --i){ 
        shiftDown(arr, n, i);        //进行循环调用
    }
    int end = n - 1;        //最后的节点依次减1
    while (end > 0){         //end>0继续循环
        Swap(arr, end, 0);        //交换函数
        shiftDown(arr, end, 0);    //交换最后一个
        --end;        //直到end=0,循环结束
    }
}