八大排序算法

冒泡排序

最简单的排序方法之一，且看其定义。

定义：

冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地遍历待排序的列表，比较每对相邻的项目，如果它们的顺序错误就把它们交换过来。遍历列表的工作是重复地进行直到没有再需要交换，也就是说该列表已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

以下是冒泡排序的步骤：

（1）比较相邻的元素。如果第一个比第二个大（升序排序），就交换它们两个；

（2）对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数；

（3）针对所有的元素重复以上的步骤，除了最后一个；

（4）重复步骤1~3，直到排序完成。

冒泡排序是一种交换排序，即通过交换元素之间的位置来完成排序，话不多说，我们使用例子来说明一下，以升序为例。

例：

待排序序列：

首先令1和3比较，1<3，不动，

3<37，不动，

37<21,交换，得

37>10，交换，得

37>5,交换，得

37>9，交换，得

37>13，交换，得

37<55，不动

55<98,不动

一趟结束，98归位，第一个大数沉淀

1<3,不动，

3<21,不动，

21>10,交换，得

21>5，交换，得

21>9，交换，得

21>13，交换，得

21<37，不动

37<55,不动

55归位（98已归位，无须再比）

1<3,不动

3<10,不动

10>5，交换，得

10>9,交换，得

可以发现，现在已经有序了，但是按照算法还会继续执行，这一趟我们在大脑里算一下，应当是37归位，之后21,13,10,9,5,3,1依次归位，但是就做了很多无用功，所以可以改进一下，设置一个标志位，当发生交换时标志位为1，未交换时为0，当未交换时，表示已经有序，直接退出即可。

下面我们用代码来实现一下

for(int i=0;i<arr.length-1;i++){
    for(int j=0;j<arr.length-1-i;j++){
        if(arr[i]>arr[j+1]){
            int temp=arr[j];
            arr[j]=arr[j+1];
            arr[j]=temp;
        }
    }
}

非常简单，两层循环，时间复杂度 $O(n^{2})$ ,改进一下

void bubbleSort(int arr[], int n) {
    bool swapped;
    for (int i = 0; i < n - 1; i++) {
        swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换 arr[j] 和 arr[j+1]
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                
                swapped = true;
            }
        }
        // 如果这一轮没有发生交换，则数组已经排序完成
        if (!swapped) {
            break;
        }
    }
}

快速排序

交换排序的王中王，速度极快，适用于大量无序数据，如果有序，效率最低。

定义：

快速排序的步骤如下：

（1）选择基准（Pivot）：在数据集之中，选择一个元素作为"基准"（pivot）。
（2）分区（Partitioning）：将数组进行分区，将小于基准的元素移到基准的左边，大于基准的元素移到基准的右边。分区完成后，基准元素所处的位置就是最终排序后它的位置。
（3）递归排序：递归地将小于基准的子序列和大于基准的子序列排序。
（4）合并：由于快速排序是在原地进行排序，不需要合并步骤，当递归到子序列只有一个元素时，递归结束，整个数组已经排序完成。

例：

待排序序列：

设置两个指针，分别指向最左边和最右边的位置

以37为基准元素

首先从对面开始比较，因为现在不确定对面是大是小，37<98,high左移

37>35，交换，low右移，此时基准元素变到右边了，必须从对面开始移动

3<37,low右移，

1<37,low右移，

21<37,low右移，

10<37，low右移，

5<37,low右移，

9<37,low右移，

13<37,low右移，

37归位，左边全是比它小的，右边全是比它大的。

第二趟左边以35开始，右边只有98，只能以它开始（这里是数据的问题，右边是可能有更多元素的，均是以部分开头的数据作为基准元素）

左边

35>13,交换

low右移

3<35,low右移，根据观察，后面几个元素都小于35，所以我们直接可以知道，不会发生交换了，35归位，这是我们人脑分析出来的，实际上计算机还是会执行，大家如果做题千万要注意不要死板地去用算法，人不是机器，我们可以快速得出一些规律的。

右边98归位

以13为基准元素

13>9，交换

low右移

3,1均小于13，直接到21,21>13，交换

high左移（注意此时基准元素变位置了，指针移动方向变了）

13>5,交换

low右移（又变了）

10<13,low右移，13归位

左边以9为基准元素，右边只有21

9<10,high左移，

9>5，交换

low右移

可知，不会变了，到9归位，同时21归位

继续，左5右10

5>1,交换，

已经到这种地步了，结果显而易见了，5,10归位

随后1归位

3归位

排序完成

大家可以看见，我们排了半天，好像不是那么快啊，其实这里是因为我选的数据基本上有序

回到最初的

后面5,9,13,35,98已经有序，所以会造成这种结果，如果全部有序的话，就更严重，所以快速排序最好处理无序的元素，因为他是不断二分的，只要先确定的元素在中间，必定会截成几段，这样就可以并行处理，速度是很快的，其时间复杂度为 $O\left ( nlogn \right )$ ，但是相比其他同样是 $O\left ( nlogn \right )$ 的算法，一般要快很多，毕竟数据量很大的时候不太可能局部有序过多。

代码实现

// 交换两个元素的值
void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

// 这个函数负责找到分区点并进行数组元素的交换
int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // 选择最后一个元素作为基准
    int i = (low - 1); // 较小元素的索引

    for (int j = low; j <= high - 1; j++) {
        // 如果当前元素小于或等于pivot
        if (arr[j] <= pivot) {
            i++; // 增加较小元素的索引
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

// 快速排序函数
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // pi是分区索引，arr[pi]现在在正确的位置
        int pi = partition(arr, low, high);

        // 递归地分别对分区前后的数组进行排序
        quickSort(arr, low, pi - 1);  // 递归排序左子数组
        quickSort(arr, pi + 1, high); // 递归排序右子数组
    }
}

递归版比较简单，非递归的简直是神中神，在此不做介绍。

简单选择排序

原理很简单，就是每次选出一个最小的或者最大的，放在一端，然后最后一个选出来就排完了。

定义：

简单选择排序是一种基本的排序算法。其工作原理是在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

例：

设置一个min来保存最小的值,先设为第一个的值，逐个比较，如果a[i]>min,下一个，a[i]<min,交换他们的值。

min=1（第一个元素是1）

1<23,下一个

1<2,下一个

......

1<99

1是最小的，1归位（哈哈，相当于没变，我故意写个小的迷惑大家）

min=23，

23>2,min=2

依次比下去2最小

注意这里是选出来插入的，所以后面空了一个就直接推过去，相对顺序不会变，所以选择排序是稳定的。

时间复杂度 $O(n^2)$ ,没有冒泡排序那种变数，这个必须把每一个元素都选一遍。

代码实现：

void swap(int *xp, int *yp) {
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}

void selectionSort(int arr[], int n) {
    int i, j, min_idx;

    // 移动未排序数组的边界
    for (i = 0; i < n-1; i++) {
        // 找到最小元素的索引
        min_idx = i;
        for (j = i+1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }

        // 将找到的最小元素与第i个位置的元素交换
        swap(&arr[min_idx], &arr[i]);
    }
}

堆排序

选择排序改进版，使用了一种堆结构，

先来看堆结构的定义：

设有一个数组a[ ]

大根堆：

a[i]>a[2i]且a[i]>a[2i+1]

小根堆

a[i]<a[2i]且a[i]<a[2i+1]

这个可能不是很直观，但是咱们可以有别的办法来表示，比如说二叉树。大家观察一下，有没有想到什么有意思的数据结构？

没错！完全二叉树。

如果我们按照层序对完全二叉树编号，那么完全二叉树的每个结点的左子树的编号就是根结点的两倍，右子树的编号就是两倍加一，看到这里我想说什么大家应该很清楚了吧。

其实根堆就是两个子树的值均大于或小于根的完全二叉树

以下为一个小根堆，对应

所以堆排序就是每次重构根堆，然后把根结点输出，跟简单选择排序就一样了，关键在于怎么构建根堆，以小根堆为例：

（1）按照层序构建一课完全二叉树

（2）调整，从最后面开始，首先左子树与右子树比较，较小的与根结点比较，如果小于根结点，则交换，逐步往上，注意是一层一层比较的。

（3）输出，交换根结点和最后一个结点，重构小根堆

（4）递归

例：

构建初始二叉树

很明显不是小根堆

调整

68>34，不变

5<21<26,5和26交换

5<23<34,5和23交换

1<46<99，不变

1<5<35,1和35交换

至此建立完成

输出1，把68换上去（最后一个元素）

这个时候下面肯定是稳定的，所以先从上面调。

5<35<68

5和68换

23<34<68,23和68换

21<26<68,21和68换

完成，输出5

23<35<68,23和68换

21<34<68,21和68换

21<23<35,21和23交换（注意先检查这一层有没有被破坏，再往下走）

26<68，交换

输出21

很讨厌，68又上去了，我随便打的数据，哈哈哈。

23<35<68,23和68换

26<34<68,26和68换

输出23

变成46了，有点意思了

26<35<46，26和46换

34<46<68,34和46换

输出26

34<35<99,34和99换

46<68<99,46和99换

输出34

35<46<99,35和99换

输出35

46<68<99,46和68交换

输出46

68<99，交换

输出68

就剩这哥们儿了，输出。

可见越到后面越快，时间复杂度 $O(nlogn)$ 。还有，堆跟二叉排序树不一样，很不一样，二叉排序树不一定是完全二叉树，而且它必须是左<根<右，但是堆没有规定左右的大小。

代码实现：

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void heapify(int arr[], int n, int i) {
    int smallest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;

    if (l < n && arr[l] < arr[smallest])
        smallest = l;

    if (r < n && arr[r] < arr[smallest])
        smallest = r;

    if (smallest != i) {
        swap(&arr[i], &arr[smallest]);
        heapify(arr, n, smallest);
    }
}

void heapSort(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    for (int i = n - 1; i >= 0; i--) {
        swap(&arr[0], &arr[i]);
        heapify(arr, i, 0);
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; ++i)
        printf("%d ", arr[i]);
    printf("\n");
}

直接插入排序

这个也很简单，就是从头到尾选择元素插入，先放第一个，然后第二个跟它比，比它小就放左边，比它大就放右边，后面的继续。

例：

放入1

放入5

放入2

放入45

放入21

放入19

放入24

放入78

放入87

放入25

完成，简单，但是要比较很多次，数据大的话基本上还不如冒泡排序，估计比选择排序好点。

代码实现：

void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;

        // 将大于key的元素向后移动
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

希尔排序

改进的插入排序，每次排一组，每组是按照一个增量来确定的。

比如如下数据

假设初始增量为d=4（通常取表长一半左右）

分成了四组，每组直接插入排序，得

然后增量折半,d=2

分成两组，组内排序

增量折半,d=1

最终结果为

代码实现：

void shellSort(int arr[], int n) {
    // 初始增量
    int gap = n / 2;
    while (gap > 0) {
        // 进行插入排序
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j;
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
        // 折半减小增量
        gap /= 2;
    }
}

感觉相当简单啊

归并排序

神中神，完全跟之前的排序不一样，采用分治法，先分解再合并，合并的时候排序。

例：

我就不多说了，代码实现如下：

// 用于合并两个子数组的函数
void merge(int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1; // 左子数组的长度
    int n2 = r - m;     // 右子数组的长度

    // 创建临时数组
    int L[n1], R[n2];

    // 拷贝数据到临时数组 L[] 和 R[]
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    // 合并临时数组到原数组 arr[l..r]
    i = 0; // 初始化第一个子数组的索引
    j = 0; // 初始化第二个子数组的索引
    k = l; // 初始化合并后数组的索引
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // 拷贝 L[] 的剩余元素
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    // 拷贝 R[] 的剩余元素
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// l 是左索引，r 是右索引
void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        // 找到中间索引
        int m = l + (r - l) / 2;

        // 分别对左右两半进行排序
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);

        // 合并两个排序好的子数组
        merge(arr, l, m, r);
    }
}

基数排序

这个我感觉很有意思，是利用位数来排的，比如十进制的数，我们就设置十个队列。

数据如下：

123

2345

100

首先看个位数，依次放进队列里面，然后再顺序输出。

100

123

2345

十位

100

123

2345

百位

100

123

2345

千位（其实已经完成了，但是算法还会继续执行的）

100

123

2345

万位

100

123

2345

完成（算法到这里才算结束）

代码实现：

/ 获取数组中的最大值
int getMax(int arr[], int n) {
    int mx = arr[0];
    for (int i = 1; i < n; i++)
        if (arr[i] > mx)
            mx = arr[i];
    return mx;
}

// 根据exp位对数组arr进行计数排序
void countSort(int arr[], int n, int exp) {
    int output[n]; // 输出数组
    int i, count[10] = {0}; // 初始化计数数组

    // 统计每个位上数字的出现次数
    for (i = 0; i < n; i++)
        count[(arr[i] / exp) % 10]++;

    // 修改count[i]，使其包含当前位数字在输出数组中的实际位置
    for (i = 1; i < 10; i++)
        count[i] += count[i - 1];

    // 构建输出数组
    for (i = n - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }

    // 将输出数组复制回原数组arr，此时arr已按当前位排序
    for (i = 0; i < n; i++)
        arr[i] = output[i];
}

// 主函数，使用基数排序对数组arr进行排序
void radixSort(int arr[], int n) {
    // 找到数组中的最大值，以确定排序需要多少位
    int m = getMax(arr, n);

    // 对每一位进行计数排序，exp是10的i次方，i是当前处理的位数
    for (int exp = 1; m / exp > 0; exp *= 10)
        countSort(arr, n, exp);
}

各种排序算法的比较

标签：arr,八大,int,元素,交换,算法,数组,排序
From： https://blog.csdn.net/czw200264/article/details/143084573

冒泡排序

快速排序

简单选择排序

堆排序

直接插入排序

希尔排序

归并排序

基数排序

各种排序算法的比较

相关文章

赞助商

阅读排行