参考视频-轻松搞定十大经典排序算法

image.png

基本排序算法的时间空间复杂度

比较类排序和非比较类排序

• 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破o(nlogn),因此也称为非线性时间比较类排序
• 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序

基本概念

• 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面
• 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面
• 时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律
• 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数

1.交换排序

交换的基础代码

数组中的两个元素进行交换

    def swap(self, arr, i , j):
        arr[i] = arr[i] ^ arr[j]
        arr[j] = arr[i] ^ arr[j]
        arr[i] = arr[i] ^ arr[j]

1.1冒泡排序 (Bubble Sort)

冒泡排序（英语：Bubble Sort）又称为泡式排序，是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

伪代码

 1.比较索引j,j+1相邻的两个元素，如果arr[j] > arr[j + 1]，就swap(j,j + 1)
 2.扫描全部数据，将最大的值交换到最后的索引位置，并将索引长度减1
 3.重复1.2步骤

代码

python

方法 一
def bubbleSort(self, arr: List[int]) -> List:
    for i in range(len(arr) - 1):
        for j in range(0, len(arr) - i - 1):
            if arr[j] > arr[j + 1]:
                self.swap(arr,j, j + 1)
    return arr
    
 方法 二
def bubbleSort1(self, arr: List[int])-> List:
    n = len(arr)
    change = n - 1
    while change:
        bounds = change
        change = 0
        for j in range(0, bounds):
            if arr[j] > arr[j + 1]:
                self.swap(arr,j,j + 1)
            change = j
    return arr

C

    void bubbleSort(int arr, int n) {
         int change = n - 1;
         while (change){
              int bounds = change;
              change = 0;
              for(int i = 0; i < bounds;  i++) {
                  if(arr[i] > arr[i+1]) {
                       swap(arr, i, i+1);
                  }
                  change = i; 
              }
          }
     }

Objective-C

     - (NSMutableArray *)bubbleSortWithArray:(NSArray *)array {
    NSMutableArray *waitSortArray = [[NSMutableArray alloc] initWithArray:array];
    // exhange记录无序区的最后一个位置，也就是有序区和无序区的分界限，当exchange为0,代表已经全部移动完毕。
    NSInteger exchange = waitSortArray.count - 1;
    while (exchange) {
        // bounds 是记录下次我们的循环区间，
        NSInteger bounds = exchange;
        exchange = 0;
        for (NSInteger i = 0; i < bounds; i++) {
            if ([waitSortArray[i] integerValue] > [waitSortArray[i+1] integerValue]) {
                NSNumber *temp = waitSortArray[i];
                waitSortArray[i] = waitSortArray[i+1];
                waitSortArray[i+1] = temp;
                // 因为我们是升序，所以移动到最后一定会是无序区的最后一个位置
                exchange = i;
            }
        }
    }
    
    return waitSortArray;
}   
    

1.2 快速排序(Quick Sort)

分区交换排序（partition-exchange sort），简称快排。
快速排序利用分治来把一个数列分为两个子数列

伪代码

 1.从数列中挑出一个元素，称为基准(pivot)（一般是每个数列的第一个）
 2.重新排列数列，当前数列，比基准小的，排在基准的前面，反之，排列在基准的后面。相同的数可以排列在任意一边。当前数列排列完成，该基准大概率就会处于数列的中间位置。这个称为分区(partition)操作
 3.递归地（recursive）对小于基准值元素的子数列和大于基准值元素的子数列进行排序。

代码

js

    
function quickSort(arr, left, right) {
    var len = arr.length,
        partitionIndex,
        left = typeof left != 'number' ? 0 : left,
        right = typeof right != 'number' ? len - 1 : right;

    if (left < right) {
        partitionIndex = partition(arr, left, right);
        quickSort(arr, left, partitionIndex-1);
        quickSort(arr, partitionIndex+1, right);
    }
    return arr;
}

function partition(arr, left ,right) {     // 分区操作
    var pivot = left,                      // 设定基准值（pivot）
        index = pivot + 1;
    for (var i = index; i <= right; i++) {
        if (arr[i] < arr[pivot]) {
            swap(arr, i, index);
            index++;
        }        
    }
    swap(arr, pivot, index - 1);
    return index-1;
}

function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
function partition2(arr, low, high) {
  let pivot = arr[low];
  while (low < high) {
    while (low < high && arr[high] > pivot) {
      --high;
    }
    arr[low] = arr[high];
    while (low < high && arr[low] <= pivot) {
      ++low;
    }
    arr[high] = arr[low];
  }
  arr[low] = pivot;
  return low;
}

function quickSort2(arr, low, high) {
  if (low < high) {
    let pivot = partition2(arr, low, high);
    quickSort2(arr, low, pivot - 1);
    quickSort2(arr, pivot + 1, high);
  }
  return arr;
}

C

Objective-C

2 插入排序

2.1 直接插入排序

插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到{\displaystyle O(1)}{\displaystyle O(1)}的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

伪代码

 1.从第一个元素开始，该元素可以认为已经被排序
 2.取出下一个元素，在已经排序的元素序列中从后向前扫描
 3.如果该元素（已排序）大于新元素，将该元素移到下一位置
 4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
 5.将新元素插入到该位置后
 6.重复步骤2~5

代码

python

    def insertionSort(self, arr: List[int]) -> List:
        if len(arr) < 1:
            return arr
        for i in range(1,len(arr)):
            k = arr[i]
            j = i - 1
            while j >= 0 and arr[j] > k:
                arr[j + 1] = arr[j]
                j -= 1
            arr[j + 1] = k
        return arr
                
                

C

void insertionSort(int arr, int n) {
        for (int i = 1; i < n; i++) {
             int k = arr[i];
             for (int j = i - 1;j>= 0; j--) {
                 if (arr[j] > k) {
                     arr[j+1] = arr[j];
                 }
             }
             arr[j + 1] = k;
        }
   }

Objective-C

// @[@1,@11,@9,@8,@2,@8,@1];
- (NSMutableArray *)straightInsertionSortWithArray:(NSArray *)array {
    NSMutableArray *waitSortArr = [[NSMutableArray alloc] initWithArray:array];
    
    // 如果数据元素只有一个或者没有，直接返回当前的数据
    if (waitSortArr.count <= 1) {
        return waitSortArr;
    }
    
    // 第0个元素为初始的有序区，后面的为无序区
    for (int i = 1; i < waitSortArr.count; i++) {
        int tempSentinel = [waitSortArr[i] intValue];
        int changeIndex = i;
        for (int j = i - 1; j >= 0 && tempSentinel < [waitSortArr[j] intValue] ; j--) { // 此处要保证j是大于0的。
            waitSortArr[j+1] = waitSortArr[j];
            changeIndex = j;
        }
        waitSortArr[changeIndex] = @(tempSentinel);
    }
    
    return waitSortArr;
}

2.2希尔排序

步长的选择是希尔排序的重要部分。只要最终步长为1任何步长序列都可以工作。算法最开始以一定的步长进行排序。然后会继续以一定步长进行排序，最终算法以步长为1进行排序。当步长为1时，算法变为普通插入排序，这就保证了数据一定会被排序。

伪代码

 1.选择一个增量序列t1，t2，…，tk，其中t1 > t2，tk=1；
 2.按增量序列个数k，对序列进行k 趟排序；
 3.每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

代码

python

    def shellSort(self, arr: List) -> List:
        if len(arr) < 1:
            return arr
        n = len(arr)
        d = n // 2
        while d >= 1:
            i = d
            while i < n:
                k = arr[i]
                j = i - d
                while j >= 0 and arr[j] >= k:
                    arr[j + d] = arr[j]
                    j -= d
                arr[j + d] = k
                i += 1
            d = d // 2
        return arr     

C

void shellSort(int arr, int n) {
        for (int d = n / 2; d>= 1; d= d /2) {
            for (int i = d; i < n; i++) {
                int k = arr[i];
                for (int j = i - d; j >= 0; j -= d){
                     if(k < arr[j]) {
                         arr[j + d] = a[j];
                     }
                }
                arr[j + d] = k;
            }
        }
   }

Objective-C

/** 希尔排序是对直接插入排序的升级，d/2作为增量 */
- (NSMutableArray *)shellSortWithArray:(NSArray *)array {
    NSMutableArray *sortArr = [[NSMutableArray alloc] initWithArray:array];
    
    // 以增量递减的方式进行循环
    for (NSInteger d = sortArr.count / 2; d >=1; d = d/2) {
        // 关键点在于i++上，而不是i = i + d。虽然执行的结果一样，但是时间复杂度不一样
        for (NSInteger i = d; i < sortArr.count ; i++) {
            NSInteger tempSentinel = [sortArr[i] integerValue];
            NSInteger changeIndex = i;
            for (NSInteger j = i - d; j >= 0 && tempSentinel < [sortArr[j] integerValue]; j = j - d) {
                sortArr[j + d] = sortArr[j];
                changeIndex = j;
            }
            sortArr[changeIndex] = @(tempSentinel);
        }
    }
    
    return sortArr;
}

3 选择排序

它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

3.1 简单选择排序

伪代码

 1.

代码

Python

def selectSort(self,arr: List[int]) -> List:
    for i in range(0,len(arr)):
        index = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[i]:
                index = j
        if index != i:
            self.swap(arr, i, index)
    return arr             

C

void selectSort(int arr, int n) {
     for(int i = 0; i < n; i++) {
        int index = i;
        for (int j = i + 1; j < n;j++) {
            if(arr[j] < arr[index]) {
               index = j;
            }
        }
        if (i != index) {
           swap(arr, i, index);
        }
     }
}

Objective-C

- (NSMutableArray *)simpleSelectionSortWithArr:(NSArray *)arr {
    NSMutableArray *waitSortArr = [[NSMutableArray alloc] initWithArray:arr];
    
    for (NSInteger i = 0; i < waitSortArr.count - 1; i++) {
        NSInteger index = i;
        for (NSInteger j = i+1; j < waitSortArr.count; j++) {
            if ([waitSortArr[j] integerValue] < [waitSortArr[index] integerValue]) {
                index = j;
            }
        }
        if (index != i) {
            NSNumber *temp = waitSortArr[i];
            waitSortArr[i] = waitSortArr[index];
            waitSortArr[index] = temp;
        }
    }
    return waitSortArr;
}

3.2 堆排序

堆排序不懂就看他-->堆排序(heapsort)

伪代码

 1.最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
 2.创建最大堆（Build Max Heap）：将堆中的所有数据重新排序
 3.堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算

代码

Python

# 堆排序
    def heapSort(self, arr: List[int]) -> List:

        # 最大堆调整
        def heapfit(arr: List[int], parentIdx: int, n: int):

            # recursion terminal
            if parentIdx > n:
                return

            # process logic in current level
            cl = 2 * parentIdx + 1
            cr = 2 * parentIdx + 2
            maxIdx = parentIdx

            if cl < n and arr[cl] > arr[maxIdx]:
                maxIdx = cl

            if cr < n and arr[cr] > arr[maxIdx]:
                maxIdx = cr

            if maxIdx != parentIdx:
                self.swap(arr, maxIdx, parentIdx)

                # dill down
                heapfit(arr, maxIdx, n)

        # 创建堆
        def buildHeap(arr: List[int], n: int):
            begin = (n - 1) // 2
            for i in range(begin, -1, -1):
                # 从 (n - 1) // 2 开始
                # n 为要构建的堆的数组长度，这个是会变得，因为在排序的时候堆的长度会减一
                heapfit(arr, i, n)

        # 堆排序
        n = len(arr)
        # 先创建第一个堆
        buildHeap(arr, n)
        for i in range(n - 1, -1, -1):
            # self.swap(arr,0, i)
            arr[i], arr[0] = arr[0], arr[i]
            buildHeap(arr, i)
        return arr

C

// 堆排序
void heapSort(int arr[], int n) {
     buildHeap(arr,n);
     for(int i = n - 1; i >= 1; i--) {
         swap(arr,i,0);
         buildHeap(arr,i);
     }
}

// 创建堆
void buildHeap(int arr[], int n) {
     index begin = (n - 1) / 2;
     for (int i = begin; i >= 0; i--) {
         heapfit(arr, n, i);
     }
}

// 堆的第一层筛选
void heapfit(int arr,int n , int index) {
     if(index > n) {
        return;
     }
     int cl = (2 * index) + 1;
     int cr = (2 * index) + 2;
     int max = index;
     if(cl < n && arr[cl] > arr[index]) {
         max = cl;
     }
     if(cr < n && arr[cr] > arr[index]) {
         max = cr;
     }
     if(max != index) {
        swap(arr, max, index);
        heapfit(arr, n, max);
     }
}

Objective-C

/** 堆排序 */
- (NSMutableArray *)heapSortWithArr:(NSArray *)arr {
    NSMutableArray *waitSortSrr = [[NSMutableArray alloc] initWithArray:arr];
    
    waitSortSrr = [self buildHeapWithArr:waitSortSrr size:waitSortSrr.count - 1];
    
    for (NSInteger i = waitSortSrr.count - 1; i >= 0; i--) {
        [self swapWithArr:waitSortSrr index:0 max:i];
        [self buildHeapWithArr:waitSortSrr size:i];
    }
    
    return waitSortSrr;
}

// 创建堆第2步 n次筛选后将整个数组置为堆
- (NSMutableArray *)buildHeapWithArr:(NSMutableArray *)arr size:(NSInteger)size{
    // 从(n-1) / 2开始
    NSInteger last_node = size - 1;
    NSInteger beginNode = (last_node - 1) / 2;
    for (NSInteger i = beginNode; i >= 0; i--) {
        [self heapifyWithArr:arr size:size - 1 index:i];
    }
    return arr;
}

/// 创建堆第1步（第一次筛选）
/// @param arr 要创建成堆的数组
/// @param size 数组的长度
/// @param index 要进行少选的结点
- (NSMutableArray *)heapifyWithArr:(NSMutableArray *)arr size:(NSInteger)size index:(NSInteger)index {
    NSMutableArray *tempArr = arr;
    if (index >= size) {
        return tempArr;
    }
    NSInteger cl = 2 * index + 1;
    NSInteger cr = 2 * index + 2;
    NSInteger max = index;
    if (cl <= size && [arr[cl] integerValue] > [arr[max] integerValue]) {
        max = cl;
    }
    if (cr <= size && [arr[cr] integerValue] > [arr[max] integerValue]) {
        max = cr;
    }
    
    if (index != max) {
        arr = [self swapWithArr:arr index:index max:max];
        tempArr = [self heapifyWithArr:arr size:size index:max];
    }
    return tempArr;
}

/** 数据交换 */
- (NSMutableArray *)swapWithArr:(NSMutableArray *)arr index:(NSInteger)index max:(NSInteger)max {
    NSNumber *temp = arr[index];
    arr[index] = arr[max];
    arr[max] = temp;
    return arr;
}

4.归并排序

采用分治法:
 1.分割：递归地把当前序列平均分割成两半。
 2.集成：在保持元素顺序的同时将上一步得到的子序列集成到一起（归并）。

4.1 二路归并排序

伪代码

 1.申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
 2.设定两个指针，最初位置分别为两个已经排序序列的起始位置
 3.比较两个指针所指向的元素，选择相对较小的元素仿佛到合并空间，并移动指针到下一个位置
 4.重复步骤3，直到某一指针到达序列尾
 5.将另一序列剩下的所有元素直接复制到合并序列尾

代码

Python

from typing import List
class Solution:
    def twoWayMergeSrot(self, arr: List[int], left: int, right: int):

        if left == right:
            return

        # 一次合并 print(leftArrSize, i, m, left, right)
        def merge(arr, left, m, right):
            leftArrSize = m - left
            rightArrSize = right - m + 1
            i, j, k = 0, 0, left
            leftArr = arr[left : m]
            rightArr = arr[m : right + 1]
            while i < leftArrSize and j < rightArrSize:
                if leftArr[i] <= rightArr[j]:
                    arr[k] = leftArr[i]
                    i += 1
                    k += 1
                else:
                    arr[k] = rightArr[j]
                    j += 1
                    k += 1

            while i < leftArrSize:
                arr[k] = leftArr[i]
                i += 1
                k += 1
            while j < rightArrSize:
                arr[k] = rightArr[j]
                j += 1
                k += 1
        # 开始分治
        m = (left + right) // 2
        self.twoWayMergeSrot(arr, left, m)
        self.twoWayMergeSrot(arr, m + 1, right)
        merge(arr, left, m + 1, right)

        return arr
a = Solution()
print(a.twoWayMergeSrot([5, 4, 5, 3, 1, 7], 0, 5))

C

void merge_sort_recursive(int arr[], int reg[], int start, int end) {
    if (start >= end)
        return;
    int len = end - start, mid = (len >> 1) + start;
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;
    merge_sort_recursive(arr, reg, start1, end1);
    merge_sort_recursive(arr, reg, start2, end2);
    int k = start;
    while (start1 <= end1 && start2 <= end2)
        reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
    while (start1 <= end1)
        reg[k++] = arr[start1++];
    while (start2 <= end2)
        reg[k++] = arr[start2++];
    for (k = start; k <= end; k++)
        arr[k] = reg[k];
}

void merge_sort(int arr[], const int len) {
    int reg[len];
    merge_sort_recursive(arr, reg, 0, len - 1);
}

Objective-C

- (NSMutableArray *)mergeSortWithArr:(NSMutableArray *)arr resultArr:(NSMutableArray *)resultArr s:(NSInteger)s t:(NSInteger)t {
    
    if (s == t) {
        return resultArr;
    }

    NSInteger m = (s + t - 1) / 2;
    [self mergeSortWithArr:arr resultArr:resultArr s:s t:m];
    [self mergeSortWithArr:arr resultArr:resultArr s:m + 1 t:t];
    [self mergeWithArr:arr resultArr:resultArr s:s m:m t:t];
    
    return resultArr;
}

/** 一次归并算法 */
- (NSMutableArray *)mergeWithArr:(NSMutableArray *)arr resultArr:(NSMutableArray *)resultArr s:(NSInteger)s m:(NSInteger)m t:(NSInteger)t{
    
    NSInteger i = s;
    NSInteger j = m + 1;
    NSInteger k = i;
    while (i <= m && j <= t) {
        if ([arr[i] integerValue] <= [arr[j] integerValue]) {
            resultArr[k++] = arr[i++];
        }else {
            resultArr[k++] = arr[j++];
        }
    }
    
    if (i <= m) {
        while (i <= m) {
            resultArr[k++] = arr[i++];
        }
    }else if (j <= t) {
        while (j <= t) {
            resultArr[k++] = arr[j++];
        }
    }
    // 返回排好序的数组
    return resultArr;
}

非比较类排序

5.计数排序

计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

伪代码

 1.找出待排序的数组中最大和最小的元素；
 2.创建空间为maxValue + 1 空间大小的数组arr
 3.统计原数组中每个值为i的元素出现的次数，并将次数存入arr的第i个索引的位置
 4.此时已经按照顺序存储了原数组中的各项元素的次数
 5.遍历arr，当arr中对应索引的元素次数不为0时，按照每个元素的存储的次数依次放入原数组。

代码

Python

    def countingSort(self, arr: List[int]) -> List:
        n = len(arr)
        maxValue = max(arr)
        res = [0] * (maxValue + 1)
        sortIndex = 0

        // 3.统计原数组中每个值为i的元素出现的次数，并将次数存入arr的第i个索引的位置
        for i in range(len(arr)):
            res[arr[i]] += 1
            
        // 5.遍历arr，当arr中对应索引的元素次数大于0时，按照每个元素的存储的次数依次放入原数组。
        for j in range(len(res)):
            while res[j] > 0:
                arr[sortIndex] = j
                sortIndex += 1
                res[j] -= 1
        return arr

6.基数排序

基本思想：收集 + 分配
也叫桶排序或箱排序：设置若干个箱子，将关键字为k的记录放入第k个箱子，然后再按序号将非空的连接。
基数排序：数字是由范围的，均由0-9这10个数字组成，则只需设置10个箱子，相继按个，十，百进行排序。

伪代码

 1. 首先有十个桶，每个桶按照当前位数值的大小，将当前数值的出现次数记录到对应数值的索引的桶中
 2. 对桶中的次数从左到右进行累加
 3. 对应次数就是对应的原数值要存储到result数组中的索引
 4. 从个位数到最大数的最大位，依次执行 1-3步

代码

Python

# 基数排序
    def radixSort(self, arr: List[int]) -> List:
        # 针对不同的指数进行一次基数排序
        # arr:原数组 iexp:指数
        def _radixSort(arr, exp) -> List:
            n = len(arr)
            result = [0] * n
            buckets = [0] * 10
            # 将个位数的出现次数按照个位数值的大小存放到以个位数值大小为索引的桶中
            for i in range(n):
                buckets[(arr[i] // exp) % 10] += 1

            # 将存放的个位数值的次数依次相加
            for i in range(1,len(buckets)):
                buckets[i] = buckets[i - 1] + buckets[i]

            # 每个桶相加后的数值就是原数组当前次数的存放索引
            for i in range(n - 1, -1, -1):
                iexp = (arr[i] // exp) % 10
                result[buckets[iexp] - 1] = arr[i]
                buckets[iexp] -= 1
                
            return result

        maxValue = max(arr)
        iexp = 1

        res = arr
        while maxValue // iexp:
            res = _radixSort(res,iexp)
            iexp *= 10

        return res

7.桶排序

伪代码

代码

Python

参考文章

• 维基百科-排序算法
• 十大经典排序算法（动图演示）
• 视频-轻松搞定十大经典排序算法
  *菜鸟
• 排序算法是基础，理解各种排序算法，最有效的方式就是多写！！！