种种排序算法统计

排序算法是最大旨最常用的算法,不一样的排序算法在区其余光景或利用中会有例外的显示,大家须求对各类排序算法熟谙才能将它们拔取到骨子里当中,才能更好地发挥它们的优势。明天,来计算下各类排序算法。

下边这些表格总括了各样排序算法的复杂度与安定:

各样排序算法复杂度相比.png

冒泡排序

冒泡排序可谓是最经典的排序算法了,它是按照相比较的排序算法,时间复杂度为O(n^2),其亮点是达成简单,n较小时质量较好。

  • 算法原理
    紧邻的多少开展两两相比较,小数放在前方,大数放在前面,那样一趟下来,最小的数就被排在了第一人,第②趟也是这么,如此类推,直到全数的数码排序已毕

  • c++代码完结

void bubble_sort(int arr[], int len)
{
for (int i = 0; i < len – 1; 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;
}
}
}
}
“`

选拔排序

  • 算法原理
    先在未排序体系中找到最小(大)成分,存放到排序种类的胚胎地点,然后,再从剩余未排序成分中继承搜寻最小(大)成分,然后嵌入已排序序列的末尾。以此类推,直到所有因素均排序完结。

  • c++代码落成

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

插入排序

  • 算法原理
    将数据分为两部分,有序部分与无序部分,一先河有序部分含有第2个因素,依次将无序的要素插入到平稳部分,直到全数因素有序。插入排序又分为间接插入排序、二分插入排序、链表插入等,那里只谈谈直接插入排序。它是稳定的排序算法,时间复杂度为O(n^2)

  • c++代码完毕

    void insert_sort(int arr[], int len)
    {
        for (int i = 1; i < len; i ++)
        {
            int j = i - 1;
            int k = arr[i];
            while (j > -1 && k < arr[j] )
            {
                arr[j + 1] = arr[j];
                j --;
            }
            arr[j + 1] = k;
        }
    }
    

迅猛排序

  • 算法原理
    高速排序是时下在实践中国和澳国常快捷的一种排序算法,它不是平安的排序算法,平均时间复杂度为O(nlogn),最差情形下复杂度为O(n^2)。它的骨干考虑是:通过一趟排序将要排序的数额分割成单身的两有的,其中有的的全体数据都比此外一些的具有数据都要小,然后再按此方法对那两某些数据分别举行高效排序,整个排序进度可以递归举行,以此达到整个数据变成有序种类。
  • c++代码落成

void quick_sort(int arr[], int left, int right)
{
if (left < right)
{
int i = left, j = right, target = arr[left];
while (i < j)
{
while (i < j && arr[j] > target)
j–;
if (i < j)
arr[i++] = arr[j];

        while (i < j && arr[i] < target)
            i++;
        if (i < j)
            arr[j] = arr[i];
    }
    arr[i] = target;
    quick_sort(arr, left, i - 1);
    quick_sort(arr, i + 1, right);
}

}
“`

归并排序

  • 算法原理
    归并排序具体做事原理如下(假使体系共有n个成分):

    • 将系列每相邻多少个数字举行联合操作(merge),形成floor(n/2)个体系,排序后各个连串包罗五个要素
    • 将上述体系再一次联合,形成floor(n/4)个种类,每一种连串包罗多个要素
    • 重复步骤2,直到全体因素排序完成

    归并排序是平静的排序算法,其时间复杂度为O(nlogn),若是是应用链表的达成的话,空间复杂度可以达到O(1),但假若是运用数组来囤积数据以来,在联合的进度中,要求权且空间来囤积归并好的数目,所以空间复杂度为O(n)

  • c++代码完成

    void merge(int arr[], int temp_arr[], int start_index, int mid_index, int end_index)
    {
        int i = start_index, j = mid_index + 1;
        int k = 0;
        while (i < mid_index + 1 && j < end_index + 1)
        {
            if (arr[i] > arr[j])
                temp_arr[k++] = arr[j++];
            else
                temp_arr[k++] = arr[i++];
        }
        while (i < mid_index + 1)
        {
            temp_arr[k++] = arr[i++];
        }
        while (j < end_index + 1)
            temp_arr[k++] = arr[j++];
    
        for (i = 0, j = start_index; j < end_index + 1; i ++, j ++)
            arr[j] = temp_arr[i];
    }
    
    void merge_sort(int arr[], int temp_arr[], int start_index, int end_index)
    {
        if (start_index < end_index)
        {
            int mid_index = (start_index + end_index) / 2;
            merge_sort(arr, temp_arr, start_index, mid_index);
            merge_sort(arr, temp_arr, mid_index + 1, end_index);
            merge(arr, temp_arr, start_index, mid_index, end_index);
        }
    }
    

堆排序

二叉堆

二叉堆是截然二叉树只怕近似完全二叉树,满意几个特色

  • 父结点的键值总是凌驾或等于(小于或等于)任何一个子节点的键值
  • 种种结点的左子树和右子树都以二个二叉堆

当父结点的键值总是凌驾或等于任何3个子节点的键值时为最大堆。当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。一般二叉树简称为堆。

堆的贮存

貌似都以数组来存储堆,i结点的父结点下标就为(i – 1) / 2。它的左右子结点下标分别为2 * i + 12 * i + 2。如第0个结点左右子结点下标分别为1和2。存储结构如图所示:

堆结构.png

堆排序原理

堆排序的时光复杂度为O(nlogn)

  • 算法原理(以最大堆为例)

  • 先将启幕数据索罗德[1..n]建成七个最大堆,此堆为先河的无序区
  • 再将重大字最大的记录中华V[1](即堆顶)和无序区的末尾八个记录Evoque[n]换来,由此赢得新的无序区翼虎[1..n-1]和逐步区Odyssey[n],且满足R[1..n-1].keys≤R[n].key
  • 是因为沟通后新的根汉兰达[1]想必违反堆性质,故应将近期无序区本田UR-V[1..n-1]调动为堆。
  • 重复二 、3步骤,直到无序区唯有1个要素结束。

  • c++代码完结

/**
 * 将数组arr构建大根堆
 * @param arr 待调整的数组
 * @param i   待调整的数组元素的下标
 * @param len 数组的长度
 */
void heap_adjust(int arr[], int i, int len)
{
    int child;
    int temp;

    for (; 2 * i + 1 < len; i = child)
    {
        child = 2 * i + 1;  // 子结点的位置 = 2 * 父结点的位置 + 1
        // 得到子结点中键值较大的结点
        if (child < len - 1 && arr[child + 1] > arr[child])
            child ++;
        // 如果较大的子结点大于父结点那么把较大的子结点往上移动,替换它的父结点
        if (arr[i] < arr[child])
        {
            temp = arr[i];
            arr[i] = arr[child];
            arr[child] = temp;
        }
        else
            break;
    }
}

/**
 * 堆排序算法
 */
void 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--)
    {
        // 将第1个元素与当前最后一个元素交换,保证当前的最后一个位置的元素都是现在的这个序列中最大的
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        // 不断缩小调整heap的范围,每一次调整完毕保证第一个元素是当前序列的最大值
        heap_adjust(arr, 0, i);
    }
}

未完待续