四种排序方法

选择排序

​ 选择排序是一种直观的排序思想，简单来说，就是从未排序的数列中找出最大或最小的元素，放在起始地址，接下来在从剩下未排序的数列中选择次小的元素放在第二位置，以此类推。

for(i=0;i<end;i++)
    for(j=i+1;j<end;j++)
        if(a[i]>a[j])
        {
            temp=a[j];
            a[j]=a[i];
            a[i]=temp;
        }

算法复杂度为O( $n^2$),不稳定。

插入排序

​ 插入排序原理很简单，一组数据分成两组，有序组与无序组。每次从无序组中取出一个元素，与有序组的元素进行比较，并找到合适的位置，将该元素插到有序组当中。就这样，每次插入一个元素，有序组增加，待插入组减少，直到无序组元素个数为0。插入排序不需要额外空间。

for(i=1;i<end;d++)
{
	temp=a[i];
	for(j=i;j>0;j--)
	{
		if(a[j]<a[j-1])
		{
		a[j]=a[j-1];
		a[j-1]=temp;
		}
	}
}

算法复杂度O($n^2$),稳定。

冒泡排序

​ 重复遍历排序的元素列，依次比较两个相邻的元素，如果顺序错误就把他们交换过来，最大或最小元素放到最后面。直到没有相邻元素需要交换，也就是说该元素列已经排序完成。

for (i=0; i<a; i++) /* 外循环为排序趟数，len个数进行len-1趟 */
        for (j=0; j<a-i; j++) { /* 内循环为每趟比较的次数，第i趟比较len-i次 */
            if (arr[j] > arr[j+1]) { /* 相邻元素比较，若逆序则交换（升序为左大于右，降序反之） */
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
}

算法复杂度O($n^2$), 稳定。

快速排序

​ 快速排序是一种分治排序算法，是解决一般问题的最佳排序算法，不需要额外的存储空间。处理大型数据集时，快速排序是一个比较好的选择。

​ 快速排序思想可以分为三个步骤：

1. 设定一个分割值并将数据分为两部分。

2. 分别在两部分运用递归的方法继续使用快速排序法。

3. 对分割部分排序直至完成。

   int qusort(int a[], int start, int end)
   {
       int i, j, down, key, temp;
       i = start;
       j = end;
       if (i >= j)
           return 0;
       key = a[i];               //设置a[i]为基准数
    while (i < j)
       {
           while (i < j && key <= a[j])
               j--;
           a[i] = a[j];
           while (i < j && key >= a[i])
               i++;
           a[j] = a[i];
       }
       a[i] = key;
   
       qusort(a, start, i - 1);
       qusort(a, i + 1, end);
       return 0;
   }

   算法复杂度O($nlogn$),不稳定。

算法复杂度和算法稳定性

​ ♦算法时间复杂度：算法的时间复杂度反映了程序执行时间随输入规模增长而增长的量级，在很大程度上能很好反映出算法的优劣与否。

​ ♦算法稳定性：在待排序的数据中，存在多个相同的数据，经过排序之后，他们的相对顺序依旧保持不变，实际上就是说array[i]=array[j],i<j.就是array[i]在array[j]之前，那么经过排序之后array[i]依旧在array[j]之前，那么这个排序算法稳定，否则，这个排序算法不稳定。

常用排序算法的复杂度和稳定性

冒泡排序是最慢的排序算法。在实际运用中它是效率最低的算法。它通过一趟又一趟地比较数组中的每一个元素，使较大的数据下沉，较小的数据上升。

插入排序通过将序列中的值插入一个已经排好序的序列中，直到该序列结束。插入排序是对冒泡排序的改进。它比冒泡排序快两倍。一般不用在数据的值大于 1000 的场合，或数据的个数超过 200 的序列。

选择排序在实际应用中处于与冒泡排序基本相同的地位。它们只是排序算法发展的初级阶段，在实际中使用较少。但是它们最好理解。

快速排序是大规模递归的算法，它比大部分排序算法都要快。一般用于数据个数比较多的情况。尽管可以在某些特殊的情况下写出比快速排序快的算法，但是就通常情况而言，没有比它更快的了。快速排序是递归的，对于内存非常有限的机器来说，它不是一个好的选择。

打赏