# 程序员必须掌握的8大排序算法

sort.jpg

## 一、直接插入排序

1-1.jpg

### （二）代码实现（Java）

```import java.util.Arrays;
public class Sort {
public static void insertSort(int[] array) {
int i, j, temp;
for (i = 1; i < array.length; i++) {
temp = array[i];
j = i;
// 将大于temp的值整体后移一个单位
while(j > 0 && array[j-1] > temp)
{
array[j] = array[j-1];
j--;
}
array[j]=temp;
}
}
public static void main(String[] args) {
int[] arr = {57, 68, 59, 52};
System.out.println("Original array: " + Arrays.toString(arr));
insertSort(arr);
System.out.println("Sorted array: " + Arrays.toString(arr));
}
}```

```Original array: [57, 68, 59, 52]
Sorted array: [52, 57, 59, 68]```

（2）i = 2，temp = a[2] = 59， ① j = 2，array[1] = 68 > temp，执行循环array[2] = array[1] = 68，j自减。 ② j = 1, array[0] = 57 > temp不成立，循环结束。 ③ 最后执行array[1] = temp = 59，此时arr = {57，59，68，52}

（3）i = 3，temp = a[3] = 52 ① j = 3, array[2] = 68 > temp，执行循环array[3] = array[2] = 68，j自减 ② j = 2，array[1] = 59 > temp，执行循环array[2] = array[1] = 59，j自减 ③ j = 1，array[0] = 57 > temo，执行循环array[1] = array[0] = 57，j自减后变为0，循环结束 ④ 最后执行array[0] = temp = 52，此时array = {52, 57, 59, 68}

## 二、希尔排序

2-1.png

2-2.png

2-3.png

2-4.png

2-5.png

2-6.png

2-7.png

### （三）代码

1 C语言实现

```#include<stdio.h>
void swap(int &a, int &b)
{
a ^= b;
b ^= a;
a ^= b;
}
void shellsort(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]);
}
void main()
{
int arr[] = {49, 38, 65, 97, 76, 13, 27, 48, 55, 4};
printf("Original array: ");
int i;
int len = sizeof(arr)/sizeof(int);
for(i = 0; i < len; i++)
{
printf("%d  ", arr[i]);
}
printf("\n");
shellsort(arr, len);
printf("Sorted array: ");
for(i = 0; i < len; i++)
{
printf("%d  ", arr[i]);
}
printf("\n");
}```

2 Java实现

```package com.z;
import java.util.Arrays;
public class Sort {
public static void shellSort(int[] array) {
int i, j, gap;
int len = array.length;
for (gap = len / 2; gap > 0; gap /= 2) {
for (i = gap; i < len; i++) {
for (j = i - gap; j >= 0 && array[j] > array[j + gap]; j -= gap) {
// 交换 两个数
array[j] ^= array[j + gap];
array[j + gap] ^= array[j];
array[j] ^= array[j + gap];
}
}
}
}
public static void main(String[] args) {
int[] arr = {49, 38, 65, 97, 76, 13, 27, 48, 55, 4};
System.out.println("Original array: " + Arrays.toString(arr));
shellSort(arr);
System.out.println("Sorted array: " + Arrays.toString(arr));
}
}```

3 运行结果

```Original array: [49, 38, 65, 97, 76, 13, 27, 48, 55, 4]
Sorted array: [4, 13, 27, 38, 48, 49, 55, 65, 76, 97]```

## 三、简单选择排序

3-1.jpg

### （二）编程实现

1 Java实现

```package com.z;
import java.util.Arrays;
public class Sort {
public static void selectSort(int[] array) {
int j, minIndex;
for (int i = 0; i < array.length - 1; i++) {
minIndex = i;
for (j = i + 1; j < array.length; j++) {
if (array[j] < array[minIndex]) {
minIndex = j;
}
}
if(minIndex != i) {
array[minIndex] ^= array[i];
array[i] ^= array[minIndex];
array[minIndex] ^= array[i];
}
}
}
public static void main(String[] args) {
int[] arr = {57, 68, 59, 52};
System.out.println("Original array: " + Arrays.toString(arr));
selectSort(arr);
System.out.println("Sorted array: " + Arrays.toString(arr));
}
}```

```Original array: [57, 68, 59, 52]
Sorted array: [52, 57, 59, 68]```

2 C语言实现

```#include<stdio.h>
void select_sort(int a[],int n)
{
int i, j, min;
for(i = 0; i < n - 1; i++)
{
min = i;
for(j = i + 1; j < n; j++)
{
if(a[j] < a[min])
{
min = j;
}
}
if(min != i)
{
a[min] = a[min] ^ a[i];
a[i] = a[min] ^ a[i];
a[min] = a[min] ^ a[i];
}
}
}
int main()
{
int b[] = {5, 4, 3, 2, 1};
int len = sizeof(b) / sizeof(int);
select_sort(b, len);
for(int i = 0; i < len; i++)
{
printf("%d ",b[i]);
}
printf("\n");
return 0;
}```

`1 2 3 4 5`

3 C++函数模板实现

```#include <iostream>
using namespace std;
#ifndef ARRAY_BASED_SORTING_FUNCTIONS
#define ARRAY_BASED_SORTING_FUNCTIONS
template<class T>
void Swap(T &x, T &y)
{
x = x ^ y;
y = x ^ y;
x = x ^ y;
}
template<class T>
void SelectionSort(T a[], int n)
{
int i, j, min;
for(i = 0; i < n-1; i++)
{
min = i;
for(j = i + 1; j < n; j++)
{
if(a[j] < a[min])
{
min = j;
}
}
if(min != i)
{
Swap(a[i], a[min]);
}
}
}
#endif
int main()
{
int a[] = {14, 12, 10, 8, 11, 4, 2};
int len = sizeof(a) / sizeof(int);
SelectionSort(a, len);
for (int i = 0; i < len; i++)
{
cout << a[i] << ' ';
}
cout << endl;
return 0;
}```

`2 4 8 10 11 12 14`

## 四、堆排序

### （三）操作过程

a）初始化堆：将R[1..n]构造为堆； b）将当前无序区的堆顶元素R[1]同该区间的最后一个记录交换，然后将新的无序区调整为新的堆。 因此对于堆排序，最重要的两个操作就是构造初始堆和调整堆，其实构造初始堆事实上也是调整堆的过程，只不过构造初始堆是对所有的非叶节点都进行调整。

### （四）例子和代码

4-1.jpg

4-2.jpg

4-3.jpg

4-4.jpg 上图中因为16，7，17三个节点不满足堆的性质，因此需要重新调整如下图：

4-5.jpg

```#include <stdio.h>
void HeapAdjust(int *a,int i,int size)  //调整堆
{
// 如果i是叶子 节点就不用进行调整
if(i >= size/2)
{
return;
}
// i非叶子节点，开始调整
int lchild = 2 * i + 1;     // i的左孩子节点序号
int rchild = 2 * i + 2;     // i的右孩子节点序号
int max = i;                // 临时变量
if(lchild < size && a[lchild] > a[max])
{
max = lchild;
}
if(rchild < size && a[rchild] > a[max])
{
max = rchild;
}
if(max != i)
{
// 将a[i]与a[max]对换
a[i]   = a[i] ^ a[max];
a[max] = a[i] ^ a[max];
a[i]   = a[i] ^ a[max];
// 若调整之后以max为父节点的子树不是堆，则对该子树继续调整
}
}
void BuildHeap(int *a,int size)
{
for(int i = size/2 - 1; i >= 0; i--)    //非叶节点最大序号值为size/2
{
}
}
int main(int argc, const char * argv[])
{
int a[] = {16, 7, 3, 20, 17, 8};
int size = sizeof(a) / sizeof(int);
BuildHeap(a, size);     // 建立堆
printf("构造出初始堆");
for(int i = 0; i < size; i++)
{
printf("%d ", a[i]);
}
return 0;
}```

`构造出初始堆  20 17 8 7 16 3`

b）有了初始堆之后，就可以进行排序

4-6.jpg

4-7.jpg

4-8.jpg

4-9.jpg

4-10.jpg

4-11.jpg

4-12.jpg

4-13.jpg

4-14.jpg

4-15.jpg

4-16.jpg

```#include <stdio.h>
void HeapAdjust(int *a,int i,int size)  //调整堆
{
// 如果i是叶子 节点就不用进行调整
if(i >= size/2)
{
return;
}
// i非叶子节点，开始调整
int lchild = 2 * i + 1;     // i的左孩子节点序号
int rchild = 2 * i + 2;     // i的右孩子节点序号
int max = i;                // 临时变量
if(lchild < size && a[lchild] > a[max])
{
max = lchild;
}
if(rchild < size && a[rchild] > a[max])
{
max = rchild;
}
if(max != i)
{
// 将a[i]与a[max]对换
a[i]   = a[i] ^ a[max];
a[max] = a[i] ^ a[max];
a[i]   = a[i] ^ a[max];
// 若调整之后以max为父节点的子树不是堆，则对该子树继续调整
}
}
void BuildHeap(int *a,int size)
{
for(int i = size/2 - 1; i >= 0; i--)    //非叶节点最大序号值为size/2
{
}
}
void HeapSort(int *a,int size)    //堆排序
{
BuildHeap(a, size);
for(int i = size - 1; i > 0; i--)
{
// 交换堆顶和最后一个元素，即每次将剩余元素中的最大者放到最后面
a[i] = a[i] ^ a[0];
a[0] = a[i] ^ a[0];
a[i] = a[i] ^ a[0];
}
}
int main(int argc, const char * argv[])
{
int a[] = {16, 7, 3, 20, 17, 8};
int size = sizeof(a) / sizeof(int);
HeapSort(a, size);     // 堆排序
printf("堆排序后的结果 ");
for(int i = 0; i < size; i++)
{
printf("%d ", a[i]);
}
return 0;
}```

`堆排序后的结果 3 7 8 16 17 20`

## 五、冒泡排序

5-1.png

### （二）代码实现

1 C语言实现

```#include <stdio.h>
void bubbleSort(int a[], int n)
{
for(int round = 0; round < n - 1; round++)
{
for(int i = 0; i < n - 1 - round; i++)
{
if(a[i] > a[i+1])
{
a[i] = a[i] ^ a[i+1];
a[i+1] = a[i] ^ a[i+1];
a[i] = a[i] ^ a[i+1];
}
}
}
}
int main()
{
int a[5] = {5, 3, 4, 1, 2};
bubbleSort(a, 5);
for (int i = 0; i < 5; i++)
{
printf("%d ", a[i]);
}
return 0;
}```

`1 2 3 4 5 `

2 C++函数模板实现

```#include <iostream>
using namespace std;
#ifndef ARRAY_BASED_SORTING_FUNCTIONS
#define ARRAY_BASED_SORTING_FUNCTIONS
template<class T>
void Swap(T &x,T &y)
{
T temp;
temp=x;
x=y;
y=temp;
}
template<class T> void BubbleSort(T A[],int n)
{
int i,j;
int lastExchangeIndex;
i=n-1;
while(i>0)
{
lastExchangeIndex=0;
for(j=0;j<i;j++)
{
if(A[j+1]<A[j])
{
Swap(A[j],A[j+1]);
lastExchangeIndex=j;
}
}
i=lastExchangeIndex;
}
}
#endif
int main()
{
int a[] = {57, 68, 59, 52};
int len = sizeof(a) / sizeof(int);
BubbleSort(a, len);
for (int i = 0; i < len; i++)
{
cout << a[i] << ' ';
}
cout << endl;
return 0;
}```

`52 57 59 68`

## 六、快速排序

6-1.png

### （三）C++代码实现

```#include <iostream>
using namespace std;
void QuickSort(int a[], int low, int high)
{
if(low >= high)
{
return;
}
int pivot = a[low];
int i = low + 1;
int j = high;
while(i <= j)
{
if(a[i] <= pivot)
{
i++;
}
else if(a[j] > pivot)
{
j--;
}
else
{
// swap a[i], a[j]
a[i] = a[i] ^ a[j];
a[j] = a[i] ^ a[j];
a[i] = a[i] ^ a[j];
i++;
j--;
}
}
// swap a[low] , a[j]
a[low] = a[j];
a[j] = pivot;
j--;
QuickSort(a, low, j);
QuickSort(a, i, high);
}
void PrintArrary(int data[], int size)
{
for (int i = 0; i < size; ++i)
{
cout << data[i] << " ";
}
cout << endl;
}
int main(int argc, const char** argv)
{
int array[]= {5, 9, 2, 7, 8, 3, 6, 1, 4, 0};
int size = sizeof(array)/sizeof(int);
QuickSort(array, 0, size - 1);
PrintArrary(array, size);
return 0;
}```

`0 1 2 3 4 5 6 7 8 9`

## 七、归并排序

7-1.jpg

### （二）代码实现

```package com.z;
import java.util.Arrays;
public class Sort {
public static void mergeSort(int[] array) {
sort(array, 0, array.length - 1);
}
private static void sort(int[] data, int left, int right) {
if (left < right) {
// 找出中间索引
int center = (left + right) / 2;
// 对左边数组进行递归
sort(data, left, center);
// 对右边数组进行递归
sort(data, center + 1, right);
// 合并
merge(data, left, center, right);
}
}
private static void merge(int[] data, int left, int center, int right) {
int[] tmpArr = new int[data.length];
int centerNext = center + 1;
// 记录临时数组的索引
int tmp = left;
int index = left;
while (left <= center && centerNext <= right) {
//从两个数组中取出最小的放入临时数组
if (data[left] <= data[centerNext]) {
tmpArr[tmp++] = data[left++];
} else {
tmpArr[tmp++] = data[centerNext++];
}
}
// 若右边数组还有剩余元素，把这些剩余元素依次放入临时数组
while (centerNext <= right) {
tmpArr[tmp++] = data[centerNext++];
}
// 若左边数组还有剩余元素，把这些剩余元素依次放入临时数组
while (left <= center) {
tmpArr[tmp++] = data[left++];
}
// 将临时数组中的内容复制回原数组
while (index <= right) {
data[index] = tmpArr[index++];
}
}
public static void main(String[] args) {
int[] arr = {52, 57, 59, 68, 28, 33, 72, 96};
System.out.println("Original array: " + Arrays.toString(arr));
mergeSort(arr);
System.out.println("Sorted array: " + Arrays.toString(arr));
}
}```

```Original array: [52, 57, 59, 68, 28, 33, 72, 96]
Sorted array: [28, 33, 52, 57, 59, 68, 72, 96]```

## 八、基数排序

8-1.jpg

### （二）代码实现

```package com.z;
import java.util.ArrayList;
import java.util.Arrays;
public class Sort {
public static void radixSort(int[] array) {
//获取最大的数
int max = array[0];
for (int i = 1; i < array.length; i++) {
if (array[i] > max) {
max = array[i];
}
}
int digitCount = 0;
//判断位数，位数即排序的趟数
while (max > 0) {
max /= 10;
digitCount++;
}
//建立10个数组;
ArrayList<ArrayList<Integer>> list = new ArrayList<>();
for (int i = 0; i < 10; i++) {
ArrayList<Integer> list1 = new ArrayList<>();
}
//进行digitCount次分配和收集;
for (int i = 0; i < digitCount; i++) {
//分配数组元素;
for (int num : array) {
//得到数字的第i+1位数;
int x = num % (int)Math.pow(10, i + 1) / (int)Math.pow(10, i);
ArrayList<Integer> list2 = list.get(x);
list.set(x, list2);
}
int index = 0;
//重新排列数组中的元素
for (int k = 0; k < 10; k++) {
while (list.get(k).size() > 0) {
ArrayList<Integer> list3 = list.get(k);
array[index] = list3.get(0);
list3.remove(0);
index++;
}
}
}
}
public static void main(String[] args) {
int[] arr = {135, 242, 192, 93, 345, 11, 24, 19};
System.out.println("Original array: " + Arrays.toString(arr));
System.out.println("Sorted array: " + Arrays.toString(arr));
}
}```

```Original array: [135, 242, 192, 93, 345, 11, 24, 19]
Sorted array: [11, 19, 24, 93, 135, 192, 242, 345]```

0 条评论

• ### 2006北京市小学生程序设计友谊赛详细答案

分析： 祖冲之密率355/113是圆周率pi的近似值。 注意： 本题第一个输入输出样例有误。输入为4时，输出应为5。 算法实现：

• ### 桶排序

3. 桶排序        桶排序的思想是若待排序的记录的关键字在一个明显有限范围内(整型)时，可设计有限个有序桶，每个桶装入一个值（当然也可以装入若干个值），...

• ### 剑指Offer-构建乘积数组

package Array; import sun.security.util.Length; /** * 构建乘积数组 * 给定一个数组A[0,1,....

• ### Codeforces Round #549（div1）简析

正解貌似有分四种情况什么的，我做时是发现各个起点其实都等价的，所以随便选一个起点，再暴举终点以暴举答案，更新即可。

• ### POJ Test for Job(DAG上拓扑排序)

题意是给了n个点，m条边(单向边)，然后每个点都有一个点权(存在负权)，问从入度为0的点开始到出度为0的点，最大的权值和为多少。

• ### leetcode 204题求素数个数

Count the number of prime numbers less than a non-negative number, n

• ### POJ 3020 Antenna Placement(二分图最小边覆盖)

题意是有一个n*m的地图，图中'*'表示城市，现在要给每个城市覆盖无线，需要安装基站，每个基站最多只能覆盖相邻的两个城市，也就是1*2或者2*1的...

• ### 2017年中国大学生程序设计竞赛-中南地区赛暨第八届湘潭市大学生计算机程序设计大赛题解&源码(A.高斯消元，D,模拟，E,前缀和，F,LCS，H,Prim算法，I,胡搞，J,树状数组)

A-------------------------------------------------------------------------------...