<返回更多

七大排序算法详细介绍

2019-06-11    
加入收藏

排序的相关概念

排序的分类

1.内排序

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

影响内排序的主要因素

内排序的分类

根据排序过程中借助的主要操作，内排序分为：

2.外排序

外排序是由于排序的记录个数太多，不能同时放置在内存中，整个排序过程需要在内外存之间多次交换数据才能进行。

按照算法的复杂度分类

 

 

一、冒泡排序算法

因为在冒泡排序中要用到顺序表结构和数组两元素的交换，先把这些写成函数

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
#define TRUE 1
#define FALSE 0
typedef struct {
 
 int r[MAXSIZE + 1];
 int length;
}SqList;
void swap(SqList *L, int i, int j){
 int temp = L->r[i];
 L->r[i] = L->r[j];
 L->r[j] = temp;
}

1.1 冒泡排序的初级版实现

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

void BubblSort0(SqList *L){
 int i,j;
 
 for (i = 1; i < L->length; i++)
 for (j = i+1; j <= L->length; j++)
 if (L->r[i] > L->r[j])
 swap(L, i, j);
}

对于这段代码，是最简单的冒泡，其实就是最简单的交换排序而已。它的思路就是让每一个关键字，都和它后面的每一个关键字比较，如果大则交换，这样第一位置的关键字在第一次循环后一定变成最小值。

假设我们待排序的关键字序列是{9，1，5，8，3，7，4，6，2}

 

算法 － 七大排序算法详细介绍

 

 

1.2 冒泡排序的实现

对于上面的算法，代码虽然简单易懂，但是效率非常低。可以改进成接下来的代码

void BubbleSort(SqList *L){
 int i,j;
 for (i = 1; i < L->length; i++)
 for (j = L->length - 1; j >= i; j--)
 if (L->r[j] > L->r[j+1])
 swap(L, j, j+1);
}

代码解释

假设我们待排序的关键字序列是{9，1，5，8，3，7，4，6，2}

1.3 冒泡排序的优化

void BubbleSort1(SqList *L){
 int i,j;
 
 int flag = TRUE;
 for (i = 1; i < L->length && flag; i++) {
 flag = FALSE;
 for (j = L->length - 1; j >= i; j--) {
 if (L->r[j] > L->r[j+1]) {
 swap(L, j, j+1);
 flag = TRUE;
 }
 }
 }
}

测试

#define N 9
int main(int argc, const char * argv[]) {
 
 int i;
 int d[N] = {9,1,5,8,3,7,4,6,2};
 
 SqList l0;
 for (i = 0; i < N; i++)
 l0.r[i+1] = d[i];
 l0.length = N;
 
 printf("排序前：
");
 for (i = 0; i < l0.length; i++) {
 printf("%d ", l0.r[i+1]);
 }
 printf("
");
 
 printf("1.0 初级冒泡排序结果:
");
 BubblSort0(&l0);
 for (i = 0; i < l0.length; i++) {
 printf("%d ", l0.r[i+1]);
 }
 printf("
");
 
 printf("1.1 冒泡排序结果:
");
 BubbleSort(&l0);
 for (i = 0; i < l0.length; i++) {
 printf("%d ", l0.r[i+1]);
 }
 printf("
");
 printf("1.2 优化后冒泡排序结果:
");
 BubbleSort1(&l0);
 for (i = 0; i < l0.length; i++) {
 printf("%d ", l0.r[i+1]);
 }
 printf("
");
 return 0;
}

测试结果

算法 － 七大排序算法详细介绍

 

 

 

二、简单选择排序

简单选择排序法(Simple Selection Sort)是通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i(1<=i<=n)个记录交换。

简单选择排序法的工作原理是：每一次从无序组的数据元素中选出最小（或最大）的一个元素，存放在无序组的起始位置，无序组元素减少，有序组元素增加，直到全部待排序的数据元素排完。

void SelectSort(SqList *L){
 int i, j, min;
 for (i = 1; i < L->length; i++) {
 min = i;
 for (j = i + 1; j <= L->length; j++) {
 if (L->r[min] > L->r[j])
 min = j;
 }
 
 if (i != min) 
 swap(L, i, min);
 }
}

代码说明

 

三、直接插入排序

直接插入排序(Straight Insertion Sort)的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录增1的有序表。

直接插入排序的核心思想：将一个记录插入到一个已经排序好的表中，以得到一个记录增加1的有序表。并且它把当前元素大的记录都往后移动，用以腾出“自己”该插入的位置。当n-1趟插入完成后该记录就是有序序列。

void InsertSort(SqList *L){
 int i, j;
 for (i = 2; i < L->length; i++) {
 
 if (L->r[i] < L->r[i-1]) {
 
 L->r[0] = L->r[i];
 for (j = i-1; L->r[j] > L->r[0]; j++)
 L->r[j+1] = L->r[i];
 
 L->r[j+1] = L->r[0];
 }
 }
}

代码说明

 

四、希尔排序

希尔排序是对直接插入排序的改进：

希尔排序的核心思想：希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止

void ShellSort(SqList *L){
 
 int i,j;
 
 int increment = L->length;
 
 do {
 increment = increment /3 +1;
 
 for (i = increment + 1; i < L->length; i++) {
 
 if (L->r[i] < L->r[i-increment]) {
 
 L->r[0] = L->r[i];
 
 for (j = i - increment; i >0 && L->r[0] < L->r[j]; j -= increment)
 L->r[j+increment] = L->r[j];
 
 L->r[j+increment] = L->r[0];
 }
 }
 } while (increment > 1);
}

代码说明

 

五、堆排序

堆的概念

堆是具有如下性质的完全二叉树：

算法 － 七大排序算法详细介绍

 

 

堆排序算法

堆排序（Heap Sort）是利用堆（假设是大顶堆）进行排序。

堆排序的核心思想：

 

算法 － 七大排序算法详细介绍

 

 

堆排序算法核心

堆排序算法代码实现

void HeadAdjust(SqList *L, int s, int m){
 int temp, j;
 temp = L->r[s];
 
 for (j = 2 *s; j <= m; j *= 2) {
 
 if (j < m && L->r[j] < L->r[j+1])
 j++;
 
 if (temp >= L->r[j])
 break;
 
 L->r[s] = L->r[j];
 s = j;
 }
 
 L->r[s] = temp;
}
void HeapSort(SqList *L){
 int i;
 
 for (i = L->length / 2; i>0; i--)
 HeadAdjust(L, i, L->length);
 
 for (i = L->length; i > 1; i--) {
 swap(L, 1, i);
 HeadAdjust(L, 1, i-1);
 }
}

堆排序算法代码说明

 

六、归并排序

归并排序(Merging Sort)是利用归并的思想实现的。2路归并排序的核心思想如下：

6.1归并排序的实现思路（递归实现）

归并排序的代码实现（递归实现）

#pragma - 6.归并排序(递归实现)
void Merge(int SR[], int TR[], int i, int m, int n){
 
 int j, k, l;
 
 for (j = m+1, k = i; i <= m && j <= n; k++) {
 
 if (SR[i] < SR[j])
 TR[k] = SR[i++];
 else
 TR[k] = SR[j++];
 }
 
 if (i <= m) {
 for (l=0; l <= m-i; l++)
 TR[k+l] = SR[i+l];
 }
 
 if (j <= n) {
 for (l=0; l <= n-j; l++)
 TR[k+l] = SR[j+l];
 }
}
void MSort(int SR[], int TR1[], int s, int t){
 int m;
 int TR2[MAXSIZE+1];
 
 if (s == t) {
 TR1[s] = SR[s];
 }else{
 m = (s+t)/2;
 MSort(SR, TR2, s, m);
 MSort(SR, TR2, m+1, t);
 Merge(TR2, TR1, s, m, t);
 }
}
void MergeSort(SqList *L){
 MSort(L->r, L->r, 1, L->length);
}

 

归并排序的总结（递归实现）

6.2归并排序的实现（迭代非递归实现）

用迭代实现的话，可以从最小的序列开始归并直到完成。

#pragma - 7.归并排序（迭代实现）
void MergePass(int SR[], int TR[], int s, int n){
 
 int i = 1;
 int j;
 
 while (i <= n-2*s+1) {
 Merge(SR, TR, i, i+s-1, i+2*s-1);
 i = i+2*s;
 }
 
 if (i < n-s+1)
 Merge(SR, TR, i, i+s-1, n);
 else
 for (j = i; j <= n; j++)
 TR[j] = SR[j];
}
void MergeSort2(SqList *L){
 
 int * TR = (int *)malloc(sizeof(L->length*sizeof(int)));
 int k = 1;
 
 while (k < L->length) {
 MergePass(L->r, TR, k, L->length);
 k = 2*k;
 
 MergePass(TR, L->r, k, L->length);
 k = 2*k;
 }
}

 

归并的迭代实现总结

 

七、快速排序

快速排序(Quick Sort)的基本思想是：

快速排序的实现思路

快速排序的代码实现

#pragma - 8.快速排序
int Partition(SqList * L, int low, int high){
 
 int pivotkey;
 pivotkey = L->r[low];
 
 while (low < high) {
 while (low < high && L->r[high] >= pivotkey)
 high --;
 swap(L, low, high);
 
 while (low < high && L->r[low] <= pivotkey)
 high++;
 swap(L, low, high);
 }
 
 return low;
}
void QSort(SqList *L, int low, int high){
 
 int pivot;
 if (low < high) {
 pivot = Partition(L, low, high);
 QSort(L, low, pivot-1);
 QSort(L, pivot+1, high);
 }
}
void QuickSort(SqList *L){
 QSort(L, 1, L->length);
}

 

快速排序的代码说明

快速排序的优化

  1. 优化选取枢轴
  2. 在上面的代码中，选取枢轴的方式为：
  3. pivotkey = L->r[low]，即用序列的第一个元素作为枢轴，这是理想情况下 L->r[low]是中间数。
  4. 但是对于其他情况，这种固定选取第一个关键子作为首个枢轴的方法就不是很合理。
  5. 于是可以用下面的方法优化：

三数取中(median-of-three)法代码：

 int pivotkey;
 
 int m = low + (high - low)/2;
 
 if (L->r[low] > L->r[high])
 swap(L, low, high);
 
 if (L->r[m] > L->r[high])
 swap(L, high, m);
 if (L->r[m] > L->r[low])
 swap(L, m, low);
 
 pivotkey = L->r[low];
  1. 优化不必要的交换
  2. 优化小数组时的排序方案
  3. 优化递归操作

快速排序优化后的代码

int Partition1(SqList * L, int low, int high){
 
 int pivotkey;
 
 int m = low + (high - low)/2;
 
 if (L->r[low] > L->r[high])
 swap(L, low, high);
 
 if (L->r[m] > L->r[high])
 swap(L, high, m);
 if (L->r[m] > L->r[low])
 swap(L, m, low);
 
 pivotkey = L->r[low];
 L->r[0] = pivotkey;
 
 while (low < high) {
 while (low < high && L->r[high] >= pivotkey)
 high--;
 L->r[low] = L->r[high];
 
 while (low < high && L->r[low] <= pivotkey)
 low++;
 L->r[high] = L->r[low];
 }
 
 L->r[low] = L->r[0];
 
 return low;
}
void QSort1(SqList *L, int low, int high){
 
 int pivot;
 if ((high -low) > MAX_LINEGIH_INSERT_SORT) {
 while (low < high) {
 pivot = Partition1(L, low, high);
 QSort1(L, low, pivot-1);
 
 low = pivot+1;
 }
 }else
 InsertSort(L);
}
void QuickSort1(SqList *L){
 QSort1(L, 1, L->length);
}
声明：本站部分内容来自互联网,如有版权侵犯或其他问题请与我们联系，我们将立即删除或处理。
▍相关推荐
更多资讯 >>>
Copyright @ 简易百科 V 2.0 京ICP备14042104号