9种排序算法总结

各种排序算法复杂度比较

冒泡排序

两两比较，从底往上升。

• 算法原理
  由最后一位开始，相邻两数两两比较，小的往上升，这样一趟下来，最小的数就被排在了第一位，第二趟也是如此，如此类推，直到所有的数据排序完成

• c++代码实现

void bubble_sort(int arr[], int len){ for (int i = 0; i < len="" -="" 1;="" i++)="" {="" for="" (int="" j="len" -="" 1;="" j=""> i; j--) { if (arr[j] < arr[j="" -="" 1])="" {="" int="" temp="arr[j];" arr[j]="arr[j" -="" 1];="" arr[j="" -="" 1]="temp;" }="" }="">

选择排序

固定位置，找元素

• 算法原理
  • 先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
  • 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
  • 以此类推，直到所有元素均排序完毕。
• c++代码实现

void select_sort(int arr[], int len) { for (int i = 0; i < len;="" i++)="" {="" int="" index="i;" for="" (int="" j="i" +="" 1;="" j="">< len;="" j++)="" {="" if="" (arr[j]="">< arr[index])="" index="j;" }="" if="" (index="" !="i)" {="" int="" temp="arr[i];" arr[i]="arr[index];" arr[index]="temp;" }="" }="">

插入排序

固定元素找位置

• 算法原理
  将数据分为两部分，有序部分与无序部分，一开始有序部分包含第1个元素，依次将无序的元素插入到有序部分，直到所有元素有序。插入排序又分为直接插入排序、二分插入排序、链表插入等，这里只讨论直接插入排序。它是稳定的排序算法，时间复杂度为O(n^2)
• c++代码实现

void insert_sort(int arr[], int len) { for (int i = 1; i < len;="" i="" ++)="" {="" int="" j="i" -="" 1;="" int="" k="arr[i];" while="" (j=""> -1 && k < arr[j]="" )="" {="" arr[j="" +="" 1]="arr[j];" j="" --;="" }="" arr[j="" +="" 1]="k;" }="">

快速排序

挖坑填数+分治法

• 算法原理
  • 选择一个基准元素，第一个或最后一个
  • 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分比基准小，另外一部分比基准大
  • 此时基准已经在其排好序后的位置
  • 然后再分别对这两部分数据用同样的方法进行排序，整个排序过程可以递归进行，直到整个数据变成有序序列。
    总结
    1．i =L; j = R; 将基准数挖出形成第一个坑a[i]。
    2．j--由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。
    3．i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。
    4．再重复执行2，3二步，直到i==j，将基准数填入a[i]中。
• c++代码实现

void quick_sort(int arr[], int left, int right){ if (left < right)="" {="" int="" i="left," j="right," target="arr[left];" while="" (i="">< j)="" {="" while="" (i="">< j="" &&="" arr[j]=""> target) j--; if (i < j)="" arr[i++]="arr[j];" while="" (i="">< j="" &&="" arr[i]="">< target)="" i++;="" if="" (i="">< j)="" arr[j]="arr[i];" }="" arr[i]="target;" quick_sort(arr,="" left,="" i="" -="" 1);="" quick_sort(arr,="" i="" +="" 1,="" right);="">

归并排序

• 算法原理
  假设序列共有n个元素：
  将序列每相邻两个数字进行归并操作（merge)，形成floor(n/2)个序列，排序后每个序列包含两个元素
  将上述序列再次归并，形成floor(n/4)个序列，每个序列包含四个元素
  重复步骤2，直到所有元素排序完毕

• c++代码实现

void merge(int arr[], int temp_arr[], int start_index, int mid_index, int end_index) { int first = start_index, second = mid_index + 1; int index = 0;//比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数,然后再进行比较，直到有数列为空， while (first < mid_index="" +="" 1="" &&="" second="">< end_index="" +="" 1)="" {="" if="" (arr[first]=""> arr[second]) temp_arr[index ++] = arr[second ++]; else temp_arr[index ++] = arr[first ++]; } //将另一个数列的数据依次取出即可 while (first < mid_index="" +="" 1)="" {="" temp_arr[index="" ++]="arr[first" ++];="" }="" while="" (second="">< end_index="" +="" 1)="" temp_arr[index="" ++]="arr[second" ++];="" for="" (i="0," j="start_index;" j="">< end_index="" +="" 1;="" i="" ++,="" j="" ++)="" arr[j]="temp_arr[i];" }="" void="" merge_sort(int="" arr[],="" int="" temp_arr[],="" int="" start_index,="" int="" end_index)="" {="" if="" (start_index="">< end_index)="" {="" int="" mid_index="(start_index" +="" end_index)="" 2;="" merge_sort(arr,="" temp_arr,="" start_index,="" mid_index);="" merge_sort(arr,="" temp_arr,="" mid_index="" +="" 1,="" end_index);="" merge(arr,="" temp_arr,="" start_index,="" mid_index,="" end_index);="" }="">

堆排序

• 算法原理（以最大堆为例）
  • 构建大顶堆
    • 初始化堆
    • 从最后一个非叶节点开始调整
    • 每次调节都从父左右节点中选最大的同父节点交换
    • 交换之后可能导致被交换的孩子节点不满足堆的性质，需要重新调整
  • 将堆顶元素通过最后一个元素 R[n] 交换
  • 由于交换后新堆顶可能违反堆的性质，因此需要重新调整为新堆，然后再次将 R[1]与无序区最后一个元素交换
• 不断重复，直到有序区的个数为n－1
• c++代码实现

/** * 将数组arr构建大根堆 * @param arr 待调整的数组 * @param i 待调整的数组元素的下标 * @param len 数组的长度 */void heap_adjust(int arr[], int i, int len){ int child; int temp; for (; 2 * i + 1 < len;="" i="child)" {="" child="2" *="" i="" +="" 1;="" 子结点的位置="2" *="" 父结点的位置="" +="" 1="" 得到子结点中键值较大的结点="" if="" (child="">< len="" -="" 1="" &&="" arr[child="" +="" 1]=""> arr[child]) child ++; // 如果较大的子结点大于父结点那么把较大的子结点往上移动，替换它的父结点 if (arr[i] < arr[child])="" {="" temp="arr[i];" arr[i]="arr[child];" arr[child]="temp;" }="" else="" break;="" }}/**="" *="" 堆排序算法="" */void="" heap_sort(int="" arr[],="" int="" len){="" int="" i;="" 调整序列的前半部分元素，调整完之后第一个元素是序列的最大的元素="" for="" (int="" i="len" 2="" -="" 1;="" i="">= 0; i--) { heap_adjust(arr, i, len); } for (i = len - 1; i > 0; i--) { // 将第1个元素与当前最后一个元素交换，保证当前的最后一个位置的元素都是现在的这个序列中最大的 int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // 不断缩小调整heap的范围，每一次调整完毕保证第一个元素是当前序列的最大值 heap_adjust(arr, 0, i); }}

希尔排序

分组插入排序，又称缩小增量排序

• 算法原理
  • 将整个待排元素分割成若干个序列（由相邻某个增量的元素组成）
  • 将这些序列分别进行直接插入排序
  • 缩减增量，再重复上述步骤
  • 待元素基本有序（增量足够小时）在对全体元素进行一次直接插排
• c++代码实现

void shellsort3(int a[], int n) { int i, j, gap; for (gap = n / 2; gap > 0; gap /= 2) for (i = gap; i < n;="" i++)="" for="" (j="i" -="" gap;="" j="">= 0 && a[j] > a[j + gap]; j -= gap) Swap(a[j], a[j + gap]); }

基数排序

• 算法原理
  • 首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中
  • 接下来将这些桶子中的数值重新串接起来，成为新的数列
  • 根据十位数数值来分配，重复上述步骤
  • 续进行以上的动作直至最高位数为止
• c++代码实现

//最大位数int maxbit(int data[], int n) { int d = 1; //保存最大的位数 int p = 10; for(int i = 0; i < n;="" ++i)="" {="" while(data[i]="">= p) { ![Uploading 273973-19cf4a1e58b6ebaf_927583.png . . .] p *= 10; ++d; } } return d; } //基数排序 void radixsort(int data[], int n) { int d = maxbit(data, n); int tmp[n]; int count[10]; //计数器 int i, j, k; int radix = 1; for(i = 1; i <= d;="" i++)="" 进行d次排序="" {="" for(j="0;" j="">< 10;="" j++)="" count[j]="0;" 每次分配前清空计数器="" for(j="0;" j="">< n;="" j++)="" {="" k="(data[j]" radix)="" %="" 10;="" 统计每个桶中的记录数="" count[k]++;="" }="" for(j="1;" j="">< 10;="" j++)="" count[j]="count[j" -="" 1]="" +="" count[j];="" 将tmp中的位置依次分配给每个桶="" for(j="n" -="" 1;="" j="">= 0; j--) //将所有桶中记录依次收集到tmp中 { k = (data[j] / radix) % 10; tmp[count[k] - 1] = data[j]; count[k]--; } for(j = 0; j < n;="" j++)="" 将临时数组的内容复制到data中="" data[j]="tmp[j];" radix="radix" *="" 10;="" }="" }="">

计数排序

• 算法原理
  • 遍历一遍整个数组，找出数组中最大数和最小数之间的差距 range,然后开辟一个大小为range的数组count并全部初始化为0；
  • 再次遍历整个数组，把每个元素的值映射到count的下标index(val –> (val-min))，每映射到一个index，就把count[index]加一；
  • 根据统计结果count，把数写会原数组，某个值index要写count[index]遍到原数组，这样，原数组就有序了
• c++代码实现

void CountSort(int *arr, int len){ assert(arr); if(len <= 1)="" return="" ;="" int="" max="arr[0];" int="" min="arr[0];" 统计数组中的最大值和最小值="" for(int="" i="0;" i="">< len;="" ++i)="" {="" if(arr[i]=""> max) max = arr[i]; if(arr[i] < min)="" min="arr[i];" }="" int="" range="max" +="" 1="" -="" min;="" 得到最大最小值的差距="" int="" *count="new" int[range];="" 用于记录数组中每个数字出现的次数="" for(int="" i="0;" i="">< len;="" ++i)="" 初始化="" count[i]="0;" for(int="" i="0;" i="">< len;="" ++i)="" count[="" arr[i]-min="" ]++;="" arr[i]="" -="" min="" 映射到tmp中的一个下标，该下标下的值是这个数出现的次数="" int="" index="0;" for(int="" i="0;" i="">< range;="" ++i)="" 再把临时数组记录的数分别拷贝到原数组中="" {="" while(count[i]--)="" 每个下标下拷贝对应的次数="" arr[index++]="i" +="" min;="" }}="">