七种常用排序算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了七种常用排序算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含7580字，纯文字阅读大概需要11分钟。

内容图文

七种常用排序算法

一、常见排序算法一览：

时间复杂度：是一个函数，它定量描述了该算法的运行时间。
空间复杂度：一个算法在运行过程中临时占用存储空间大小的量度。
稳定性：保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同就稳定，反之不稳定。

视觉直观感受 7 种常用的排序算法

二、算法C#实现：

1、直接插入排序：

            
                using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace csharpconsole
{
    class Program
    {
        /* 
        具体算法描述如下：
        1.从第一个元素开始，该元素可以认为已经被排序
        2.取出下一个元素，在已经排序的元素序列中从后向前扫描
        3.如果该元素（已排序）大于新元素，将该元素移到下一位置
        4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
        5.将新元素插入到该位置后
        6.重复步骤2~5
        */publicstaticvoidInsertSort(int[] List)
        {
            int tmp = 0;
            int len = List.Length;
            int i = 0;
            int j = 0;

            for (i = 1; i < len; i++)
            {
                tmp = List[i];
                for (j = i - 1; j >= 0; j--)
                {
                    if (tmp < List[j])
                    {
                        List[j + 1] = List[j];
                    }
                    elseif (tmp > List[j])
                    {
                        break;
                    }
                }
                List[j + 1] = tmp;
            }
            return;
        }

        staticvoid Main(string[] args)
        {
            int[] intArr = {10, 2, 56, 12, 6, 78, 34, 23, 9, 18, 7};

            InsertSort(intArr);

            for (int k = 0; k < intArr.Length; k++)
            Console.WriteLine(intArr[k]);
            Console.ReadKey();
        }
    }
}

2、希尔排序：
实际上是分组的插入排序。缩小增量排序。先取定一个小于n的整数d1作为第一个增量,把表的全部记录分成d1个组,所有距离为d1的倍数的记录放在同一个组中,在各组内进行直接插入排序；然后,取第二个增量d2(＜d1),重复上述的分组和排序,直至所取的增量dt=1。

            
                using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace csharpconsole
{
    class Program
    {
        publicstaticvoidShellSort(int[] List)
        {
            int tmp = 0;
            int len = List.Length;
            int i = 0;
            int j = 0;
            int d = len / 2; /* 初始步长取数组长度的一半 *//* 观察看如果d=1的话，即是普通的插入排序算法 */while (d >= 1)
            {
                /* 把距离为 d 的元素编为一个组，扫描所有组 */for (i = d; i < len; i++)
                {
                    tmp = List[i];

                    for (j = i - d; j >= 0; j = j - d)
                    {
                        if (tmp < List[j])
                        {
                            List[j + d] = List[j];
                        }
                        elseif (tmp > List[j])
                        {
                            break;
                        }
                    }
                    List[j + d] = tmp;
                }

                d = d / 2;
            }


            return;
        }

        staticvoid Main(string[] args)
        {
            int[] intArr = {10, 2, 56, 12, 6, 78, 34, 23, 9, 18, 7};

            ShellSort(intArr);

            for (int k = 0; k < intArr.Length; k++)
            Console.WriteLine(intArr[k]);
            Console.ReadKey();
        }
    }
}

3、冒泡排序（交换排序）：

            
                using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespacecsharpconsole
{classProgram
    {publicstaticvoid BubbleSort(int[] List)
        {
            int i = 0;
            int j = 0;
            int len = List.Length;
            int swap = 0;

            /* 
            第一趟排序：通过两两比较，找到第一小的数值 1 ，将其放在序列的第一位。
            第二趟排序：通过两两比较，找到第二小的数值 2 ，将其放在序列的第二位。
            第三趟排序：通过两两比较，找到第三小的数值 3 ，将其放在序列的第三位。
            至此，所有元素已经有序，排序结束。
            */for (i = len - 1; i >= 0; i--)
            {
                for (j = len - 1; j >= len - i; j--)
                {
                    if (List[j] < List[j - 1])
                    {
                        swap = List[j];
                        List[j] = List[j - 1];
                        List[j - 1] = swap;
                    }
                }
            }

            return;
        }

        staticvoid Main(string[] args)
        {
            int[] intArr = {10, 2, 56, 12, 6, 78, 34, 23, 9, 18, 7};

            BubbleSort(intArr);

            for (int k = 0; k < intArr.Length; k++)
            Console.WriteLine(intArr[k]);
            Console.ReadKey();
        }
    }
}

4、快速排序(交换排序)：
步骤：
技术分享

            
                using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespacecsharpconsole
{classProgram
    {publicstaticvoid QuickSort(int[] List, int left, int right)
        {
            int baseNum = 0;
            int low = 0;
            int high = 0;

            if (left < right)
            {
                baseNum = List[left];
                low = left;
                high = right;

                while (low < high)
                {
                    /* 从右往左扫描 */while ((high > low) && (baseNum < List[high]))
                    {
                        high--;
                    }
                    List[low] = List[high];

                    /* 从左往右扫描 */while ((low < high) && (baseNum > List[high]))
                    {
                        low++;
                    }
                    List[high] = List[low];
                }

                List[low] = baseNum;
                QuickSort(List, left, low - 1);
                QuickSort(List, low + 1, right);
            }

            return;
        }

        staticvoid Main(string[] args)
        {
            int[] intArr = {10, 2, 56, 12, 6, 78, 34, 23, 9, 18, 7};

            QuickSort(intArr, 0, intArr.Length - 1);

            for (int k = 0; k < intArr.Length; k++)
            Console.WriteLine(intArr[k]);
            Console.ReadKey();
        }
    }
}

5、简单选择排序(直接选择排序):
(1) 从待排序序列中，找到关键字最小的元素；
(2) 如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；
(3) 从余下的 N - 1 个元素中，找出关键字最小的元素，重复(1)、(2)步，直到排序结束。

            using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace csharpconsole
{
    classProgram
    {publicstaticvoid SelectionSort(int[] List)
        {
            intindex = 0;
            int swap = 0;
            int len = List.Length;
            int i = 0;
            int j = 0;

            for (; i < len; i++)
            {
                /* 找到这一趟循环最小的值，记录下标，默认下标为i */index = i;
                for (j = i + 1; j < len; j++)
                {
                    if (List[j] < List[index])
                    {
                        index = j;
                    }
                }

                /* 如果下标有改变，就交换数值 */if (index != i)
                {
                    swap = List[i];
                    List[i] = List[index];
                    List[index] = swap;
                }
            }

            return;
        }

        staticvoid Main(string[] args)
        {
            int[] intArr = {10, 2, 56, 12, 6, 78, 34, 23, 9, 18, 7};

            SelectionSort(intArr);

            for (int k = 0; k < intArr.Length; k++)
            Console.WriteLine(intArr[k]);
            Console.ReadKey();
        }
    }
}

6、堆排序：
步骤：
（1）根据初始数组去构造初始堆（构建一个完全二叉树，保证所有的父结点都比它的孩子结点数值大）。
（2）每次交换第一个和最后一个元素，输出最后一个元素（最大值），然后把剩下元素重新调整为大根堆。

            
                using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace csharpconsole
{
    class Program
    {
        publicstaticvoid HeapAdjust(int[] array, int parent, int length)
        {

            int temp = array[parent]; // temp保存当前父节点int child = 2 * parent + 1; // 先获得左孩子while (child < length)
            {
                // 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点if (child + 1 < length && array[child] < array[child + 1])
                {
                    child++;
                }

                // 如果父结点的值已经大于孩子结点的值，则直接结束if (temp >= array[child])
                {
                    break;
                }

                // 把孩子结点的值赋给父结点array[parent] = array[child];

                // 选取孩子结点的左孩子结点,继续向下筛选
                parent = child;
                child = 2 * child + 1;
            }

            array[parent] = temp;
        }

        publicstaticvoid HeapSort(int[] list)
        {
            // 循环建立初始堆for (int i = list.Length / 2; i >= 0; i--)
            {
                HeapAdjust(list, i, list.Length - 1);

            }

            // 进行n-1次循环，完成排序for (int i = list.Length - 1; i > 0; i--)
            {
                // 最后一个元素和第一元素进行交换int temp = list[i];
                list[i] = list[0];
                list[0] = temp;

                // 筛选 R[0] 结点，得到i-1个结点的堆
                HeapAdjust(list, 0, i);
            }

        }

        staticvoid Main(string[] args)
        {
            int[] intArr = {10, 2, 56, 12, 6, 78, 34, 23, 9, 18, 7};

            HeapSort(intArr);

            for (int k = 0; k < intArr.Length; k++)
            Console.WriteLine(intArr[k]);
            Console.ReadKey();
        }
    }
}

7、归并排序：
步骤：
（1）“分解”——将序列每次折半划分。
（2）“合并”——将划分后的序列段两两合并后排序。

            
                using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace csharpconsole
{
    class Program
    {
        publicstaticvoid Merge(int[] array, int low, int mid, int high)
        {
            int i = low; // i是第一段序列的下标int j = mid + 1; // j是第二段序列的下标int k = 0; // k是临时存放合并序列的下标int[] array2 = newint[high - low + 1]; // array2是临时合并序列// 扫描第一段和第二段序列，直到有一个扫描结束while (i <= mid && j <= high)
            {
                // 判断第一段和第二段取出的数哪个更小，将其存入合并序列，并继续向下扫描if (array[i] <= array[j])
                {
                    array2[k] = array[i];
                    i++;
                    k++;
                }
                else
                {
                    array2[k] = array[j];
                    j++;
                    k++;
                }
            }

            // 若第一段序列还没扫描完，将其全部复制到合并序列while (i <= mid)
            {
                array2[k] = array[i];
                i++;
                k++;
            }

            // 若第二段序列还没扫描完，将其全部复制到合并序列while (j <= high)
            {
                array2[k] = array[j];
                j++;
                k++;
            }

            // 将合并序列复制到原始序列中for (k = 0, i = low; i <= high; i++, k++)
            {
                array[i] = array2[k];
            }
        }

        publicstaticvoid MergePass(int[] array, int gap, int length)
        {
            int i = 0;

            // 归并gap长度的两个相邻子表for (i = 0; i + 2 * gap - 1 < length; i = i + 2 * gap)
            {
                Merge(array, i, i + gap - 1, i + 2 * gap - 1);
            }

            // 余下两个子表，后者长度小于gapif (i + gap - 1 < length)
            {
                Merge(array, i, i + gap - 1, length - 1);
            }
        }

        publicstaticint[] MergeSort(int[] list)
        {
            for (int gap = 1; gap < list.Length; gap = 2 * gap)
            {
                MergePass(list, gap, list.Length);
            }
            returnlist;
        }

        staticvoid Main(string[] args)
        {
            int[] intArr = {10, 2, 56, 12, 6, 78, 34, 23, 9, 18, 7};

            MergeSort(intArr);

            for (int k = 0; k < intArr.Length; k++)
            Console.WriteLine(intArr[k]);
            Console.ReadKey();
        }
    }
}

原文：http://blog.csdn.net/nobcaup/article/details/51722330

内容总结

以上是互联网集市为您收集整理的七种常用排序算法全部内容，希望文章能够帮你解决七种常用排序算法所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1105014.html

来源：【匿名】

【上一篇】数据结构-算法【下一篇】浅谈php实现映射的两种方法（链表和二叉树）

更多 ►

【七种常用排序算法】教程文章相关的互联网学习教程文章

1 #include<iostream>2usingnamespace std;3 4//************快速排序法********* 5int partiton(int array[10],int s,int t,int &cutpoint){6int x=array[s];7int i,j;8 i=s;9 j=t; 10while(i!=j){ 11while(i<j&&array[j]>x)j--; 12if(i<j){ 13 array[i]=array[j]; 14 i++; 15 } 16while(i<j&&array[i]<x)i++; 17if(i<j){ 18 array[j]=array[i]; 19 j--; 20 ...

排序算法之一---选择排序【代码】

选择排序的基本思想:每次选择未排序元素中的最小(非增序列)或者最大(非减序列)的一个一次加入到已排序序列后面,直到所有元素都排序完 #include <stdio.h> void selection_sort(int arr[],int length) {int i,j;for (i = 0; i < length; i++){int minval_index = i;for (j = i+1; j < length; j++){if (arr[j] < arr[minval_index]){minval_index = j;}}int temp = arr[i];arr[i] = arr[minval_index];arr[minval_index] = temp;} }...

常见的排序算法及其复杂度【图】

?原文：https://www.cnblogs.com/kexinxin/p/11595225.html

排序算法之冒泡排序(Bubble Sort)【代码】

基本思想　　假如按照从小到大的顺序排序，对待排序数组进行遍历，如果当前值大于其后一个值则进行交换，不断的进行遍历，直到没有交换动作的发生。冒泡排序的最好时间复杂度为O（n），最坏的时间复杂度为O（n2），所以冒泡排序的平均时间复杂度为O（n2），另外冒泡排序不会改变相同元素的前后顺序，故其是一种稳定的排序算法。实现代码#include<iostream> usingnamespace std;int main() {int MyData[10] = { 7,3,12,46,32,64,13,...

三种全排序算法详解

1、全排列的非去重递归算法算法思路：全排列可以看做固定前i位，对第i+1位之后的再进行全排列，比如固定第一位，后面跟着n-1位的全排列。那么解决n-1位元素的全排列就能解决n位元素的全排列了，这样的设计很容易就能用递归实现。附代码段：void permutation1(char* str,int sbegin,int send) //全排列的非去重递归算法 {if( sbegin == send) //当 sbegin = send时输出{for(int i = 0;i <= send; i++) //输出一个排列cout << s...

四种排序算法与二分查找【代码】

1. 冒泡排序func BubbleSort(slice []int) []int {i, j, okay, count := 0, 0, true, len(slice)for i = 0; i < count-1; i++ { //最多需要进行count-1轮比较okay = truefor j = 0; j < count-i-1; j++ { //每一轮比较的逻辑if slice[j] > slice[j+1] {slice[j], slice[j+1] = slice[j+1], slice[j]okay = false}}if okay { //当轮比较没有发生位置交换，说明已经排序完成，可提前退出循环break}}return slice } 2. 插入排序func I...

高速排序算法

高速排序算法作者 July 二零一一年一月四日------------------------------------------ 写之前，先说点题外话。每写一篇文章，我都会遵循下面几点原则：一、保持版面的尽量清晰，力保排版良好。二、力争所写的东西，清晰易懂，图文并茂三、尽最大可能确保所写的东西精准，有实用价值。由于，我认为，你既然要把你的文章，发布出来，那么你就一定要为你的读者负责。不然，就不要发表出来。一切，为读者服务。 ok，闲不多说...

python学习之排序算法【代码】

1.冒泡算法：N个数从左到右，相邻两两比较，按照顺序排列。 #冒泡排序，升序 a = [4,5,1,6,3,7,1,10] for i in range(len(a)):for j in range(i+1,len(a)):if a[i] > a[j]:a[i], a[j] = a[j], a[i] print(a)[1, 1, 3, 4, 5, 6, 7, 10]#冒泡排序，降序 a = [4,5,1,6,3,7,1,10] for i in range(len(a)):for j in range(i+1,len(a)):if a[i] < a[j]:a[i], a[j] = a[j], a[i] print(a)[10, 7, 6, 5, 4, 3, 1, 1]原文：http://blog.51ct...

【C语言】两种方式实现冒泡排序算法【代码】

题目要求编写一个C语言程序,实现基本的冒泡排序算法.算法冒泡排序,用一句话来总结:一组数中,相邻的两个数进行比较、交换,将最大(小)数交换至尾(首)部,即完成了一次冒泡排序要想对N个数字进行排序,循环N次即可.如果真的不理解冒泡排序算法,请点击:冒泡排序_360百科核心代码//方式一:从头向尾遍历,将最大数(相对)沉入尾部(相对) void BubbleSort1(int *arr,int sz){int i = 0;int j = 0;assert(arr);for(i=0;i<sz-1;i++){for(j=0;j<s...

冒泡排序算法【代码】

冒泡排序算法的时间复杂度是什么？时间复杂度是O(n^2)。 1 #include "stdafx.h" 2 #include <iostream>3usingnamespace std;4void Swap(int &a, int &b)5{6int temp = a;7 a = b;8 b = temp;9} 1011void Bubble1(int *array, int length) 12{ 13for (int i=length-1;i>0;--i) //首先是要比较多少趟，每一趟冒泡可以确定一个值。最后一趟只剩一个就不用比较了（所以是i>0而不是i>=0)。14 { 15for (int j=0;j<i;++j) 16 ...

数据结构与算法 -- Python实现【归并排序算法】【代码】【图】

摘要：本文主要介绍的是python实现归并排序算法，本文首先会介绍归并排序的原理，并以一张思维导图来加深读者对该算法过程的理解，紧接着进行代码的实现。最后介绍该算法的时间复杂度。一.原理：1.将一个序列从中间位置分成两个序列；2.在将这两个子序列按照第一步继续二分下去；3.直到所有子序列的长度都为1，也就是不可以再二分截止。这时候再两两合并成一个有序序列即可。下面的这张图片可以很清晰的解释该原理：二.代码如下...

排序算法

五，快速排序（划分交换排序）思想：（选择一个中间值作为一个分割线，分开序列）　　通过第一个值作为中值（注意这里中值并不意味着最后位置是最中间）对整个数列进行划分，然后从右开始做判断，交换进行排序，最后要求：规则：这个中值的左边都小于它，右边都大于它。　　将list[0]提出来，0位空缺　　low游标初始指向0，和high游标指向尾部，在指向空值时不能挪动。high游标先动，直到有不满足规则的，交换空缺和high的值。然...

利用归并排序算法对大文件进行排序

归并排序算法介绍，请参照Wikipeidazh.wikipedia.org/wiki/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F基本思想：大文件分割成行数相等的两个子文件，递归（归并排序）两个子文件，直到递归到分割成的子文件低于限制行数低于限制行数的子文件直接排序两个排序好的子文件归并到父文件直到最后所有排序好的父文件归并到输入的大文件并返回之前看了网上很多示例代码，写的很不简洁，引入了过多的临时变量i, j, k等等，导致程序基本没法看...

js:数据结构笔记11--排序算法（1）【代码】【图】

基本准备： function CArray(numElems) {this.dataStore = [];this.pos = 0;this.numElems = numElems;this.insert = insert;this.toString = toString;this.clear = clear;this.setData = setData;this.swap =swap;for(var i = 0; i < numElems; ++i) {this.dataStore[i] = i;}}function setData() {for(var i = 0; i < this.numElems; ++i) {this.dataStore[i] = Math.floor(Math.random() * 100);//0-99}}function clear() {...

排序算法（七）非比较排序：计数排序、基数排序、桶排序【代码】【图】

前面讲的是比较排序算法，主要有冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序等。非比较排序算法：计数排序，基数排序，桶排序。在一定条件下，它们的时间复杂度可以达到O(n)。一，计数排序（Counting Sort）(1)算法简介计数排序(Counting sort)是一种稳定的排序算法。计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排...

排序算法 - 相关标签

排序算法的时间复杂度排序算法总结

算法 - 最热教程

浅谈SQLServer查询优化器中的JOIN算法有没那种可逆算法是密文比明文短的呢？...javascript-类似Excel里面的NORMDIST函...C++中的分治算法及常见题目汇总压缩感知重构算法综述-学习笔记 c++中内置函数qsort（快速排序）和bsea...一、fpga图像处理算法整合基于遗传算法（deap）的非线性函数寻优...集成学习-Bagging集成学习算法随机森林...机器学习笔记（九）聚类算法及实践（K-...

首页 / 算法 / 七种常用排序算法

七种常用排序算法

内容导读

内容图文

七种常用排序算法

内容总结

内容备注

内容手机端

【七种常用排序算法】教程文章相关的互联网学习教程文章

1）①排序算法之交换排序[2]快速排序【代码】

排序算法之一---选择排序【代码】

常见的排序算法及其复杂度【图】

排序算法之冒泡排序(Bubble Sort)【代码】

三种全排序算法详解

四种排序算法与二分查找【代码】

高速排序算法

python学习之排序算法【代码】

【C语言】两种方式实现冒泡排序算法【代码】

冒泡排序算法【代码】

数据结构与算法 -- Python实现【归并排序算法】【代码】【图】

排序算法

利用归并排序算法对大文件进行排序

js:数据结构笔记11--排序算法（1）【代码】【图】

排序算法（七）非比较排序：计数排序、基数排序、桶排序【代码】【图】

排序算法 - 相关标签

算法 - 最新教程

算法 - 最热教程