开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 排序算法理解总结篇——冒泡排序、选择排序、插入排序、希尔排序、归并排序、堆排序、计数排序、基数排序、桶排序 -> 正文阅读

[数据结构与算法]排序算法理解总结篇——冒泡排序、选择排序、插入排序、希尔排序、归并排序、堆排序、计数排序、基数排序、桶排序

🍀排序算法-平均时间复杂度

排序算法	平均时间复杂度
冒泡排序	$O(n^2)$
选择排序	$O(n^2)$
插入排序	$O(n^2)$
希尔排序	$O(n^{1.5})$
归并排序	$O (n ? l o g N)$
堆排序	$O (n ? l o g N)$
快速排序	$O (n ? l o g N)$
计数排序	$O (n + k)$
基数排序	$O (n + k))$
桶排序	$O (n + k)$

🍀 $O(n^2)$ 的排序算法

??冒泡排序

两个数比较大小，如要求是升序排序，则较大的数往下沉，较小的数往上冒。

伪代码

BubbleSort(A)
	for i = 1 to A.length-1
		for j = A.length-1 downto i
			if A[j] < A[j - 1]
				exchange A[j] with A[j - 1]

Java版

    public int[] BubbleSort(int[] list) {
        int len = list.length;
        for (int i = 1; i < len; i++) {
            for (int j = len - 1; j >= i; j--) {
                if(list[j] < list[j-1]) {
                    int tmp = list[j];
                    list[j] = list[j-1];
                    list[j-1] = tmp;
                }
            }
        }
        return list;
    }

Java泛型版

    public <T extends Comparable<T>> T[] BubbleSort(T list[]) {
        int len = list.length;
        for (int i = 1; i < len; i++) {
            for (int j = len - 1; j >= i; j--) {
                if (list[j].compareTo(list[j - 1]) > 0) {
                    T tmp = list[j];
                    list[j] = list[j - 1];
                    list[j - 1] = tmp;
                }
            }
        }
        return list;
    }

1、时间复杂度： $O(n^2)$
2、空间复杂度： $O (1)$
3、非稳定排序
4、原地排序

??选择排序

每次选择最小或者最大的元素排列到有序区。
在长度为N的无序数组中，第一次遍历n-1个数，找到最小的数值与第一个元素交换；
第二次遍历n-2个数，找到最小的数值与第二个元素交换；
重复。。。
第n-1次遍历，找到最小的数值与第n-1个元素交换，排序完成。

伪代码

SelectionSort(A)
	for i=1 to A.length-1
	    min=i 
	    for j=i+1 to A.length
	         if A[j]<A[min]
	            min=j
	     tem=A[min]
	     A[min]=A[i]
	     A[i]=tem

Java版

    public  int[] SelectionSort(int[] list) {
        int len = list.length, minT;
        for (int i = 0; i < len; i++) {
            minT = i;
            for (int j = i + 1; j < len; j++) {
                if (list[j] <list[minT])  {
                    minT = i;
                }
            }
            int tmp = list[minT];
            list[minT] = list[i];
            list[i] = tmp;
        }
        return list;
    }

Java泛型版

    public <T extends Comparable<T>> T[] SelectionSort(T[] list) {
        int len = list.length, minT;
        for (int i = 0; i < len; i++) {
            minT = i;
            for (int j = i + 1; j < len; j++) {
                if (list[j].compareTo(list[minT]) < 0) {
                    minT = i;
                }
            }
            T tmp = list[minT];
            list[minT] = list[i];
            list[i] = tmp;
        }
        return list;
    }

1、时间复杂度： $O(n^2)$
2、空间复杂度： $O (1)$
3、非稳定排序
4、原地排序

??插入排序

在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。

伪代码

InsertionSort(A)
  for j = 2 to A.length
     key = A[j]
     i = j-1
     while i > 0 and A[i] > key
          A[i+1] = A[i]
          i = i -1
     A[i+1] = key

Java代码

    public int[] InsertionSort(int list[]) {
        int len = list.length;
        for (int i = 1; i < len; i++) {
            int tmp = list[i];
            int j = i - 1;
            // 将比插入元素值大的数往后移动
            while (j >= 0 && list[j] > tmp) {
                list[j + 1] = list[j];
                j--;
            }
            // 插入元素
            list[j + 1] = tmp;
        }
        return list;
    }

Java泛型版

    public <T extends Comparable<T>> T[] InsertionSort(T list[]) {
        int len = list.length;
        for (int i = 1; i < len; i++) {
            T tmp = list[i];
            int j = i - 1;
            // 将比插入元素值大的数往后移动
            while (j >= 0 && list[j].compareTo(tmp) > 0) {
                list[j + 1] = list[j];
                j--;
            }
            // 插入元素
            list[j + 1] = tmp;
        }
        return list;
    }

1、时间复杂度： $O(n^2)$
2、空间复杂度： $O (1)$
3、非稳定排序
4、原地排序

🍀 $O (n ? l o g N)$ 的排序算法

??希尔排序

在要排序的一组数中，根据某一增量分为若干子序列，并对子序列分别进行插入排序。
然后逐渐将增量减小,并重复上述过程。直至增量为1,此时数据序列基本有序,最后进行插入排序。

假如待排序数组基本有序，使用插入排序更有效。

伪代码

ShellSort(A)
  d=A.length
? do
?	d = d/2
?	for i = 1 to A.length - d
?     j = i + d
?	  if(A[i] > A[j]
?		exchange A[i] and A[j]
  while(d>1)

Java代码

    public int[] ShellSort(int list[]) {
        int len = list.length;
        int d = len;
        do {
            d /= 2;
            for (int i = 0; i < len - d; i++) {
                int j = i + d;
                if (list[j] < list[i]) {
                    int tmp = list[i];
                    list[i] = list[j];
                    list[j] = tmp;
                }
            }
        } while (d > 1);
        return list;
    }

Java泛型版

    public <T extends Comparable<T>> T[] ShellSort(T list[]) {
        int len = list.length;
        int d = len;
        do {
            d /= 2;
            for (int i = 0; i < len - d; i++) {
                int j = i + d;
                if (list[j].compareTo(list[i]) < 0) {
                    T tmp = list[i];
                    list[i] = list[j];
                    list[j] = tmp;
                }
            }
        } while (d > 1);
        return list;
    }

1、时间复杂度： $O (n l o g N)$ - $O(n^2)$ ，平均为 $O(n^{1.5})$
2、空间复杂度：O(1)
3、非稳定排序
4、原地排序

??归并排序

归并算法是分治思想一个经典应用。
将大的数组一直分割，直到数组的大小为 1，此时只有一个元素，那么该数组就是有序的了，之后再把两个数组大小为1的合并成一个大小为2的，再把两个大小为2的合并成4的 …… 直到全部小的数组合并起来。

归并排序的分治思想

分解：分解待排序的n个元素的序列成各具 n/2 个元素的子序列
解决：使用归并排序递归地排序子序列
合并：合并两个已经排序的子序列以产生已排序的答案。

伪代码

Merge(A, p, q, r)
    n1 = q-p+1
    n2 = r-q
    //let L[1....n1+1] and R[1....n2+1] be new arrays
    for i =1 to n1
         L[i] = A[p+i-1]
    for j=1 to n2
        R[j] = A[q+j]
    L[n1+1] = ∞
    L[n2+1] = ∞
    i=1
    j=1
    for k =p to r
        if L[i]<=R[j]
            A[k] = L[i]
            i = i + 1
        else
            A[k]=R[j]
            j = j+1

MergeSort(A,p,r)
    if p < r
        q = ?(p+r)/2?  //向下取整
        MergeSort(A, p, q)
        MergeSort(A, q+1, r)
        Merge(A, p, q, r)

Java代码

    public int[] MergeSort(int list[]) {
        int tmp[] = new int[list.length]; //在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
        MergeSort(list, 0, list.length - 1, tmp);
        return list;
    }

    public void MergeSort(int[] list, int l, int r, int tmp[]) {
        if (l < r) {
            int mid = (l + r) / 2;
            MergeSort(list, l, mid, tmp);
            MergeSort(list, mid + 1, r, tmp);
            Merge(list, l, mid, r, tmp);
        }
    }

    void Merge(int list[], int l, int mid, int r, int tmp[]) {
        int i = l; //左序列指针
        int j = mid + 1; //右序列指针
        int t = 0; //临时数组指针
        while (i <= mid && j <= r) {
            if (list[i] <= list[j]) {
                tmp[t++] = list[i++];
            } else {
                tmp[t++] = list[j++];
            }
        }
        while (i <= mid) { //将左边剩余元素填充进temp中
            tmp[t++] = list[i++];
        }
        while (j <= r) { //将右序列剩余元素填充进temp中
            tmp[t++] = list[j++];
        }
        t = 0;
        //将temp中的元素全部拷贝到原数组中
        while (l <= r) {
            list[l++] = tmp[t++];
        }
    }

1、时间复杂度： $O (n l o g N)$
2、空间复杂度： $O (n)$
3、稳定排序
4、非原地排序

??堆排序

堆的特点就是堆顶的元素是一个最值，大顶堆的堆顶是最大值，小顶堆则是最小值。
建立大顶堆；
拿掉堆顶的元素，重新构建堆；
拿掉堆顶元素，重新构建堆。。。
等到堆剩余的元素只有一个的时候，此时的数组就是有序的了。

伪代码

HeapSort(A)
  BuildMaxHeap(A)
    for i = A.length downto 2
      exchange A[1] with A[i]
      A.heap-size = A.heap-size - 1
      MaxHeapify(A, 1)
// 建立大顶堆
BuildMaxHeap(A)
  A.heap-size = A.length
  for i = int(A.length / 2) downto 1
    MaxHeapify(A, i)
//维护堆
MaxHeapify(A, i)
  l = LEFT(i)
  r = RIGHT(i)
  if l <= A.heap-size and A[l] > A[i]
    largest = l
  else largest = i
  
  if r <= A.heap-size and A[r] > A[largest]
    largest = r

  if largest <> i
    exchange A[i] with A[largest]
    MaxHeapify(A, largest)

Java代码

    public int[] HeapSort(int list[]) {
        BuildMaxHeap(list);
        for (int i = list.length - 1; i >= 0; i--) {
            int tmp = list[0];
            list[0] = list[i];
            list[i] = tmp;
            MaxHeapify(list, 0, i);
        }
        return list;
    }

    public void BuildMaxHeap(int list[]) {
        // 构建大顶堆
        int heapSize = list.length;
        for (int i = (heapSize / 2); i >= 0; i--) {
            MaxHeapify(list, i, heapSize);
        }
    }

    public void MaxHeapify(int list[], int i, int heapSize) {
        // 维护堆
        int l = LEFT(i);
        int r = RIGHT(i);
        int largest;
        if (l <= heapSize - 1 && list[l] > list[i]) {
            largest = l;
        } else {
            largest = i;
        }
        if (r <= heapSize - 1 && list[r] > list[largest]) {
            largest = r;
        }
        if (largest != i) {
            int tmp = list[i];
            list[i] = list[largest];
            list[largest] = tmp;
            MaxHeapify(list, largest, heapSize);
        }
    }

    public int PARENT(int i) {
        return (i - 1) / 2;
    }

    public int LEFT(int i) {
        return 2 * i + 1;
    }

    public int RIGHT(int i) {
        return 2 * i + 2;
    }

1、时间复杂度： $O (n l o g N)$
2、空间复杂度： $O (1)$
3、非稳定排序
4、原地排序

??快速排序

同样是分治思想。
先从数列中取出一个数作为key值；
将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边；
对左右两个小数列重复第二步，直至各区间只有1个数。

伪代码

QuickSort(A, p, r)
  if  p < r
    q = Partition(A,p,r）
    QuickSort(A,p,q-1)
    QuickSort(A,q+1,r)

Partition(A, p, r)
  x = A[r]
  i = p-1
  for j = p to r-1
    if A[j] <= x   //<=与书上有区别，符号的区别，不会打那个。。。。
      i = i + 1
      exchange A[i] with A[j]
  exchange A[i+1] with A[r]
  return i + 1

Java代码

    public int[] QuickSort(int list[]) {
        QuickSort(list, 0, list.length - 1);
        return list;
    }

    public void QuickSort(int list[], int l, int r) {
        if (l < r) {
            int mid = Partition(list, l, r);
            QuickSort(list, l, mid - 1);
            QuickSort(list, mid + 1, r);
        }
    }

    public int Partition(int list[], int l, int r) {
        int x = list[r];
        int i = l - 1;
        for (int j = l; j <= r - 1; j++) {
            if (list[j] <= x) {
                i = i + 1;
                int tmp = list[i];
                list[i] = list[j];
                list[j] = tmp;
            }
        }
        int tmp = list[i + 1];
        list[i + 1] = list[r];
        list[r] = tmp;
        return i + 1;
    }

1、时间复杂度： $O (n l o g N)$
2、空间复杂度： $O (l o g N)$
3、非稳定排序
4、原地排序

🍀 $O (n + k)$ 的排序算法、非比较排序

??计数排序

把数组元素作为数组的下标，然后用一个临时数组统计该元素出现的次数，例如 temp[i] = n, 表示元素 i 一共出现了 n 次。最后再把临时数组统计的数据从小到大汇总起来，此时汇总起来是数据是有序的。

计数排序比较适用于待排序数组中最大值和最小值相差不大的排序。

伪代码

CountingSort(A,B,k)
  let C[0..k] be a new array
  for i = 0 to k //后面需要使用数组C来存储A中各元素的出现次数，所以需要清零操作
    C[i] = 0
  for j = 1 to A.length 
    C[A[j]] = C[A[j]] + 1 //统计A中各元素的出现次数存储在C中，C中下标为A中的元素值，与其对应的数组元素为出现次数，如C[1] = 0，即为“1”在A中的出现次数为0
  for i = 1 to k 
    C[i] = C[i] + C[i-1] //计算A中小于等于i的一共有多少个，方便此后将i放在数组B中正确的位置上
  for j = A.length downto 1
    B[C[A[j]]] = A[j] //使用A中元素A[j]的出现次数作为B中的下标，把每个元素放在B中适当的位置
    C[A[j]] = C[A[j]] -1 //在B中放入一个元素，与其对应C中出现的次数-1。这样，当遇到下一个等于A[j]的输入元素时，该元素可以被直接放到B中A[j]的前一位置上

Java代码

    public int[] CountingSort(int list[]) {
        int maxNum = Arrays.stream(list).max().getAsInt();
        CountingSort(list, maxNum);
        return list;
    }

    public void CountingSort(int list[], int maxNum) {
        int tmp[] = new int[maxNum + 1];
        int res[] = new int[list.length];
        for (int item : list) {
            tmp[item]++;
        }
        for (int i = 1; i < tmp.length; i++) {
            tmp[i] += tmp[i - 1];
        }
        for (int i = list.length - 1; i >= 0; i--) {
            // 数组下标从0开始，此处减1
            res[tmp[list[i]]-1] = list[i];
            tmp[list[i]]--;
        }
    }

1、时间复杂度： $O (n + k)$ ，K：建立的计数数组长度
2、空间复杂度： $O (n + k)$
3、稳定排序
4、非原地排序

??基数排序

先以个位数的大小来对数据进行排序，接着以十位数的大小来多数进行排序，接着以百位数的大小。。。
排到最后，就是一组有序的元素了。

伪代码

RADIXSORT(A,d) // d:最高位数
  for i = 1 to d
    use a stable sort to sort array A on digit i // 从个位数至高位数依次重复排序

Java代码

    public int[] RadixSort(int list[]) {
        int maxNum = Arrays.stream(list).max().getAsInt();
        int d = 0;
        while(maxNum!=0) {
            maxNum /=10;
            d++;
        }
        RadixSort(list,d);
        return list;
    }

    public void RadixSort(int list[], int d) {
        int[] res = new int[list.length];//结果数组
        int[] tmp = new int[10];//计数数组，范围为每位上的取值范围0-9

        //一个十进制数m，它的个位数是m/1%10，十位数是m/10%10,百位数是m/100%10
        for(int i=0;i<d;i++) {
            int division = (int)Math.pow(10, i);//取个位::/1 十位:/10 百位:/100中的基本划分点
            for(int j=0;j<list.length;j++) {
                int num = list[j]/division%10;//取个位 十位 或百位上的数，每轮由此位置上的数大小进行计数排序
                tmp[num]=tmp[num]+1;//进行计数排序中计数数组的更新
            }

            //计数排序中计数数组count的累加，保证稳定性
            for(int m=1;m<tmp.length;m++) {
                tmp[m]=tmp[m]+tmp[m-1];
            }

            //计数排序中逆序遍历原数组A，根据累加后的数组count将A中每个元素正确填入result中正确的位置中
            for(int j=list.length-1;j>=0;j--) {
                int num = list[j]/division%10;
                res[tmp[num]-1]=list[j];
                tmp[num]=tmp[num]-1;
            }

            //将数组A更新为数组B
            for(int j=0;j<list.length;j++) {
                list[j]=res[j];
            }
            //将数组C清零，进行下一轮的循环
            for(int j=0;j<tmp.length;j++) {
                tmp[j]=0;
            }
        }
    }

1、时间复杂度： $O (n + k)$ ，K：建立的计数数组长度
2、空间复杂度： $O (n + k)$
3、稳定排序
4、非原地排序

??桶排序

把最大值和最小值之间的数进行瓜分，例如分成 10 个区间，10个区间对应10个桶，我们把各元素放到对应区间的桶中去，再对每个桶中的数进行排序，对桶中元素排序可采用其他排序方法。每个桶排序后再合并起来形成有序数组。

伪代码

BucketSort(A)
  n = A.length
  let B[0...n-1] be a new array
  for i = 0 to n-1
    b[i]=0
    //make B an empty list
  for i =1 to n
	insert A[i] into list B[(int)nA[i]]
  for i =0 to n-1
    sort list B[i] with insertion sort
  concatenate hte lists B[0...n-1] together in order

Java代码

	class LinkedNode {
        public int value;
        public LinkedNode next;
        public LinkedNode(int value) {
            this.value = value;
        }
    }

    public int[] BucketSort(int list[]) {
        int length = list.length;
        LinkedNode[] bucket = new LinkedNode[length];  // 桶的个数等于length
        int max = list[0];  // 求max
        for (int i = 1; i < list.length; i++) {
            if (list[i] > max) {
                max = list[i];
            }
        }
        // 入桶
        for (int i = 0; i < length; i++) {
            int value = list[i];  // 扫描每个元素
            int hash = hash(list[i], max, length);  // 桶的下标
            if (bucket[hash] == null) {
                bucket[hash] = new LinkedNode(value);  // 初始化链表
            } else {
                insertInto(value, bucket[hash], bucket, hash);  // 插入链表
            }
        }
        int k = 0; // 记录数组下标
        // 出桶，回填arr
        for (LinkedNode node : bucket) {
            if (node != null) {
                while (node != null) {
                    list[k++] = node.value;
                    node = node.next;
                }
            }
        }
        return list;
    }

    private int hash(int element, int max, int length) {
        return (element * length) / (max + 1);
    }

    private void insertInto(int value, LinkedNode head, LinkedNode[] bucket, int hash) {
        LinkedNode newNode = new LinkedNode(value);
        // 小于头节点，放在头上
        if (value <= head.value) {
            newNode.next = head;
            // 替换头节点
            bucket[hash] = newNode;
            return;
        }
        // 往后找第一个比当前值大的节点，放在这个节点的前面
        LinkedNode p = head;
        LinkedNode pre = p;
        while (p != null && value > p.value) {
            pre = p;
            p = p.next;
        }
        if (p == null) {  // 跑到末尾了
            pre.next = newNode;
        } else {             // 插入pre和p之间
            pre.next = newNode;
            newNode.next = p;
        }
    }