当前位置:   article > 正文

常见的排序算法【总结】

常见的排序算法【总结】

排序的基本概念与分类

排序就是将一组杂乱无章的数据按照一定的规律(升序或降序)组织起来。
排序问题中,通常将数据元素称为记录。 可以将排序看成是线性表的一种操作。

排序的稳定性

排序算法平均时间复杂度最好情况最坏情况空间复杂度稳定性
冒泡排序O(n2)O(n)O(n2)O(1)稳定
简单选择排序O(n2)O(n2)O(n2)O(1)不稳定
插入排序O(n2)O(n)O(n2)O(1)稳定
希尔排序O(nlogn) ~ O(n2)O(n1.3)O(n2)O(1)不稳定
堆排序O(nlogn)O(nlogn)O(nlogn)O(1)不稳定
归并排序O(nlogn)O(nlogn)O(nlogn)O(n)稳定
快速排序O(nlogn)O(nlogn)O(n2)O(logn)~O(n)不稳定

假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的。
稳定的:冒泡、插入、归并;
不稳定:选择、希尔、快速、堆排序

  • 内部排序:数据元素全部放在内存中的排序。
  • 外排排序:数据元素太多不能同时放在内存中,根据排序过程的要求不能在内外存之间移动数据的排序。

内排序与外排序

内排序是排序整个过程中,待排序的所有记录全部被放置在内存中。

  • 根据排序过程中借助的主要操作,内排序分为插入排序交换排序选择排序归并排序
    外排序是由于排序的记录个数太多,不能同时放置在内存中,整个排序过程需要在内外存之间多次交换数据才能进行。

简单排序

冒泡、选择、插入排序都是简单排序,最坏情况下的时间复杂度都是 O ( n 2 ) O(n^2) O(n2) ,二平方阶随着输入规模的增大,事件成本将急剧上升,所以这些基本排序方法不能处理更大规模的问题。

冒泡排序

冒泡排序(Bubble Sort)是一种交换排序,它的基本思想是:两两比较相邻记录的关键字,如果反序则交换,直到没有反序的记录为止。

时间复杂度: O ( n 2 ) O(n^2) O(n2)

C#代码:

public class Bubble
{
    /// <summary>
    /// 正宗的冒泡排序
    /// </summary>
    /// <param name="nums"></param>
    public void BubbleSort(int[] nums)
    {
        int i, j;
        for (i = 1; i < nums.Length; i++)
        {
            for (j = nums.Length - 1; j >= i; j--)
            {
                if (nums[j] < nums[j - 1])
                {
                    Swap(nums,j,j-1);
                }
            }
        }
    }
    /// <summary>
    /// 优化后的冒泡排序
    /// </summary>
    /// <param name="nums"></param>
    public void BubbleSort1(int[] nums)
    {
        int i, j;
        bool flag = true;
        for (i = 1; i < nums.Length && flag; i++)
        {
            flag = false;
            for (j = nums.Length - 1; j >= i; j--)
            {
                if (nums[j] < nums[j - 1])
                {
                   Swap(nums,j,j-1);
                   flag = true;
                }
            }
        }
    }
    private void Swap(int[] nums,int i, int j)
    {
        (nums[i], nums[j]) = (nums[j], nums[i]);
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46

简单选择排序

排序原理:
  1. 在待排序数组中选出最小的(或最大)的与第一个位置的数据交换 然后在剩下的待排序数组中找出最小(或最大)的与第二个位置的数据交换,以此类推,直到第n-1个元素。
  2. 简单选择排序可以说是冒泡排序的一种改版,它不再两两比较出较小数就进行交换,而是每次遍历比较当前数的后面所有数,最后再把最小的数和当前数进行交换。
时间复杂度: O ( n 2 ) O(n^2) O(n2)

image.png

C#代码:

 public void Select(int[] nums)
    {
	    int min;
        for (int i = 0; i < nums.Length-1; i++)
        {
            min = i;
            for (int j = i+1; j < nums.Length; j++)
            {
                if (nums[j]<nums[min])
                {
                    min = j;
                }
            }
            (nums[i], nums[min]) = (nums[min], nums[i]);
        }
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

插入排序

插入排序(Insertion sort)是一种简单直观且稳定的排序算法。

插入排序的工作方式非常像人们排序一手扑克牌一样。开始时,我们的左手为空并且桌子上的牌面朝下。然后,我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置,我们从右到左将它与已在手中的每张牌进行比较

排序原理:
  1. 把所有的元素分为两组,已经排序的和未排序的;
  2. 找到未排序的组中的第一个元素,向已经排序的组中进行插入
  3. 倒叙遍历已经排序的元素,依次和待插入的元素进行比较,直到找到一个元素小于等于待插入元素,那么就把待插入元素放到这个位置,其他的元素向后移动一位;
时间复杂度: O ( n 2 ) O(n^2) O(n2)

C#代码:

public void Insertion(int[] nums)
    {
        for (int i = 1; i < nums.Length; i++)
        {
            for (int j = i; j > 0; j--)
            {
                if (nums[j-1]>nums[j])
                {
	                //交换元素
                    (nums[j - 1], nums[j]) = (nums[j], nums[j - 1]);
                }else
                    break;
            }
        }
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

高级排序

希尔排序

希尔排序是插入排序的一种,又称“缩小增量排序”,是插入排序算法的一种更高效的改进版本。

前面学习插入排序的时候,我们会发现一个很不友好的事儿,如果已排序的分组元索为{2,5,7,9,10},未排序的分组元素为{1,8},那么下一个待插入元素为1,我们需要拿着1从后往前,依次和10,9,7,5,2进行交换位置,才能完成真正的插入,每次交换只能和相邻的元素交换位置。那如果我们要提高效率,直观的想法就是一次交换,能把1放到更前面的位置,比如一次交换就能把1插到2和5之间,这样-次交换1就向前走了5个位置,可以减少交换的次数,这样的需求如何实现呢?接下来我们来看看希尔排序的原理。

排序原理:
  1. 选定一个增长量h,按照增长量h作为数据分组的依据,对数据进行分组
  2. 对分好组的每一组数据完成插入排序;
  3. 减小增长量,最小减为1,重复第二步操作。
    增长量h的确定:我们这里采用以下规则:
int h = 1;
while(h<长度/2)
{
	h = 2h+1;
}
//循环结束后我们就可以确定h的最大值
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

h的减小规则为 h = h/2
image.png

C#代码:

public void Shell(int[] nums)
{
	//确定增长值
	int h = 1;
	while (h < nums.Length / 2)
	{
		h = 2 * h + 1;
	}
	while (h>=1)
	{
		//排序
		for (int i = h; i < nums.Length; i++)
		{
			for (int j = i; j >=h ; j-=h)
			{
				if (nums[j]<nums[j-h])
				{
					//交换
					(nums[j], nums[j - h]) = (nums[j - h], nums[j]);
				}
				else
				{
					break;
				}
			}
		}
		h /= 2;
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29

归并排序

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

排序原理:

归并排序算法有两个基本的操作,一个是,也就是把原数组划分成两个子数组的过程。另一个是,它将两个有序数组合并成一个更大的有序数组。

  1. 尽可能的一组数据拆分成两个元素相等的子组,并对每一个子组继续拆分,直到拆分后的每个子组的元素个数是1为止。
  2. 将相邻的两个子组进行合并成一个有序的大组;
  3. 不断的重复步骤2,直到最终只有一个组为止。
时间复杂度: O ( n l o g n ) O(nlogn) O(nlogn)
空间复杂度: O ( N ) O(N) O(N)

归并排序需要一个与原数组相同长度的数组做辅助来排序。

归并排序的缺点

需要申请额外的数组空间,导致空间复杂度提升,是典型的以空间换时间的操作

算法性能

速度仅次于快速排序。
image.png

C#代码:

//递归实现的归并排序
public class MergeSort
{
    private int[] list;
 
    private bool Less(int[] nums,int a, int b)
    {
        return nums[a] - nums[b] < 0;
    }

    public void Sort(int[] nums)
    {
        int lo = 0;
        int hi = nums.Length - 1;
        list = new int[nums.Length];
        Sort(nums,lo,hi);
    }

    private void Sort(int[] nums, int lo, int hi)
    {
        //安全性校验
        if (lo>=hi)
        {
            return;
        }
        int mi = lo + (hi - lo) / 2;
        //分别对每一组数据进行排序
        Sort(nums,lo,mi);
        Sort(nums, mi+1, hi);
        //把两个数组进行归并
        Merge(nums,lo,mi,hi);
    }

    private void Merge(int[] nums, int lo, int mi, int hi)
    {
        //定义3个指针
        int p1 = lo;
        int p2 = mi + 1;
        int p = lo;
        //编历,移动p1指针和p2指针,比较对应索引处的值,找出小的那个,放到辅助数组的对应索引处
        while (p1 <= mi && p2 <= hi)
        {
            if (Less(nums,p1,p2))
            {
                list[p++] = nums[p1++];
            }
            else
            {
                list[p++] = nums[p2++];
            }
        }
        //如果p1指针没有走完
        while (p1<=mi)
        {
            list[p++] = nums[p1++];
        }
        //如果p2指针没有走完
        while (p2<=hi)
        {
            
            list[p++] = nums[p2++];
        }

        //把辅助数组中的数据拷贝到原数组中
        for (int i = lo; i <= hi; i++)
        {
            nums[i] = list[i];
        }
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71

快速排序

快速排序是对冒泡排序的一种改进。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

时间复杂度: O ( n l o g n ) O(nlogn) O(nlogn)
排序原理:
  1. 首先设定一个分界值,通过该分界值将数组分成左右两部分;
  2. 将大于或等于分界值的数据放到到数组右边,小于分界值的数据放到数组的左边。此时左边部分中各元素都小于或等于分界值,而右边部分中各元素都大于或等于分界值;
  3. 然后,左边和右边的数据可以独立排序。对于左侧的数组数据,又可以取一个分界值,将该部分数据分成左右两部分,同样在左边放置较小值,右边放置较大值。右侧的数组数据也可以做类似处理。
  4. 重复上述过程,可以看出,这是一个递归定义。通过递归将左侧部分排好序后,再递归排好右侧部分的顺序。当左侧和右侧两个部分的数据排完序后,整个数组的排序也就完成了

image.png

切分原理:

把一个数组切分成两个子数组的基本思想

  1. 找一个基准值,用两个指针分别指向数组的头部和尾部
  2. 先从尾部向头部开始搜索一个比基准值小的元素,搜索到即停止,并记录指针的位置
  3. 再从头部向尾部开始搜索一个比基准值大的元素,搜索到即停止,并记录指针的位置
  4. 交换当前左边指针位置和右边指针位置的元素
  5. 重复2,3,4步骤,直到左边指针的值大于右边指针的值停止。

C#代码:

//快速排序主要有三个参数,left 为区间的开始地址,right 为区间的结束地址,Key 为当前的开始的值。
//我们从待排序的记录序列中选取一个记录(通常第一个)作为基准元素(称为key)key=arr[left],然后设置两个变量,left指向数列的最左部,right 指向数据的最右部。
public class QuickSort
{
    public void Sort(int[] arr)
    {
        Quick(arr, 0, arr.Length - 1);
    }

    private void Quick(int[] arr, int left, int right)
    {
        if (left < right)
        {
            int pivot = Partition(arr, left, right);
            Quick(arr, left, pivot - 1);
            Quick(arr, pivot + 1, right);
        }
    }

    private int Partition(int[] arr, int left, int right)
    {
        int pivotKey = arr[left];
        while (left < right)
        {
            while (left < right && arr[right] >= pivotKey)
            {
                right--;
            }

            arr[left] = arr[right];
            while (left < right && arr[left] <= pivotKey)
            {
                left++;
            }

            arr[right] = arr[left];
        }

        arr[left] = pivotKey;

        return left;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
快速排序和归并排序的区别:

快速排序是另外一种分治的排序算法,它将一个数组分成两个子数组,将两部分独立的排序。快速排序和归并排序是互补的:归并排席将数组分成两个子数组分别排序,并将有序的子数组归并从而将整个数组排序,而快速排序的方式则是当两个数组都有序时,整个数组自然就有序了。在归并排序中,一个数组被等分为两半,归并调用发生在处理整个数组之前,在快速排序中,切分数组的位置取决于数组的内容,递归调用发生在处理整个数组之后。

堆排序

堆排序相当于简单选择排序的升级,他们同属于选择排序类。堆的结构可以分为大顶堆和小顶堆,是一个完全二叉树,而堆排序是根据堆的这种数据结构设计的一种排序。

大顶堆和小顶堆

性质:每个结点的值都大于或等于其左孩子和右孩子结点的值,称之为大顶堆;每个结点的值都小于或等于其左孩子和右孩子结点的值,称之为小顶堆。如下图

image.png

上面的结构映射成数组
image.png

查找数组中某个数的父结点和左右孩子结点,比如已知索引为i的数,那么

1.父结点索引:(i-1)/2(这里计算机中的除以2,省略掉小数)

2.左孩子索引:2*i+1

3.右孩子索引:2*i+2

所以上面两个数组可以脑补成堆结构,因为他们满足堆的定义性质:

大顶堆:arr(i)>arr(2*i+1) && arr(i)>arr(2*i+2)

小顶堆:arr(i)<arr(2*i+1) && arr(i)<arr(2*i+2)

堆排序基本原理:
  1. 首先将待排序的数组构造成一个大顶堆,此时,整个数组的最大值就是堆结构的顶端

  2. 将顶端的数与末尾的数交换,此时,末尾的数为最大值,剩余待排序数组个数为n-1

  3. 将剩余的n-1个数再构造成大根堆,再将顶端数与n-1位置的数交换,如此反复执行,便能得到有序数组
    图片原文https://www.cnblogs.com/sunshineliulu/p/12995910.html
    C#代码:

public class HeapSort  
{  
    public static void Sort(int[] arr)  
    {  
        int n = arr.Length;  
  
        // 构建最大堆:大顶堆的构建过程就是从最后一个非叶子结点开始从下往上调整,则最后一个非叶子结点的位置是:数组长度/2-1。  
        for (int i = n / 2 - 1; i >= 0; i--)  
            Heapify(arr, n, i);  
  
        // 排序
        for (int i = n - 1; i >= 0; i--)  
        {  
            // 将当前最大的元素 arr[0] 和 arr[i] 交换  
            Swap(arr, 0, i);  
  
            // 重新调整剩余元素为最大堆  
            Heapify(arr, i, 0);  
        }  
    }  
  
    // 调整以 pos 为根的子树,使其保持最大堆的性质  
    private static void Heapify(int[] arr, int n, int pos)  
    {  
        int largest = pos; // 初始化 largest 为根  
        int left = 2 * pos + 1; // 左子节点  
        int right = 2 * pos + 2; // 右子节点  
  
        // 如果左子节点比根大  
        if (left < n && arr[left] > arr[largest])  
            largest = left;  
  
        // 如果右子节点比当前最大的还大  
        if (right < n && arr[right] > arr[largest])  
            largest = right;  
  
        // 如果最大的不是根  
        if (largest != pos)  
        {  
            // 交换  
            Swap(arr, pos, largest);  
  
            // 递归地调整受影响的子树  
            Heapify(arr, n, largest);  
        }  
    }  
  
    // 交换数组中的两个元素  
    private static void Swap(int[] arr, int i, int j)  
    {  
        (arr[i], arr[j]) = (arr[j], arr[i]);  
    }  
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53

排序算法的选择

没有十全十美的排序方法,有优点就会有缺点。即使是快速排序,也只是在整体性能上优越,它也存在排序不稳定、需要大量辅助空间、对少量数据排序无优势等不足。

空间复杂度来说,归并排序强调要马跑得快,就得给马吃个饱。快速排序也有相应的空间要求,反而堆排序等却都是少量索取,大量付出,对空间要求是0(1)。如果执行算法的软件所处的环境非常在乎内存使用量的多少时,选择归并排序和快速排序就不是一个较好的决策了。

稳定性来看,归并排序独占鳌头,我们前面也说过,对于非常在乎排序稳定性的应用中,归并排序是个好算法。

从待排序记录的个数上来说,待排序的个数n越小,采用简单排序方法越合适。反之,n越大,采用高级排序方法越合适。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/木道寻08/article/detail/766998
推荐阅读
相关标签
  

闽ICP备14008679号