排序算法
冒泡排序
从要排序序列的第一个元素开始，不断比较相邻元素的值，发现逆序则交换，将值较大的元素逐渐从前向后移动。
每找到待排序序列的最大值时，就将该最大值固定在待排序序列的尾部，且每找到一个待排序序列最大值需要循环一次，n 个值则需要循环 n 次，但最后一个值无需比较，则实际需循环 n-1 次，即 i < arr.length - 1 。
void bubbleSort (int arr[]) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
当然，该方法还可以进行优化。
定义一个布尔变量 flag，用来标记每轮是否进行了交换。在每轮遍历开始时，将 flag 设置为 false。若当轮没有发生交换，即此时 flag 依然为 false，说明此时数组已经按照升序排列。此时外层循环直接退出，排序结束。
void bubbleSort (int arr[]) {
boolean flag = false;
for (int i = 0; i < arr.length - 1; i++) {
flag = false;
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
flag = true; //该轮发生交换
}
}
if (!flag) {
break; //数组已有序
}
}
}
复杂度分析：
-
时间复杂度 O(n^2)
-
空间复杂度 O(1)
选择排序
选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。同样，选择排序也需要比较 n - 1轮，最后一轮无需比较。
void selectSort (int arr[]) {
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i; //初始化最小值索引
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) {
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
复杂度分析：
-
时间复杂度 O(n^2)
-
空间复杂度 O(1)
直接插入排序
- 数据类型定义
typedef int ElemType;
typedef struct
{
ElemType *elem; //顺序表基址，elem[0]闲置或作为监视哨
int length; //顺序表长度
} SqList;
- 算法实现
/**
* 直接插入排序
*/
void insertSort(SqList &L)
{
int i, j;
for (i = 2; i <= L.length; i++)
{
if (L.elem[i] < L.elem[i - 1])
{
//将L.elem[i]保存在空闲的0号单元，并作为哨兵
L.elem[0] = L.elem[i];
L.elem[i] = L.elem[i - 1];
//因为有哨兵L.elem[0]，所以条件 j>0 可写可不写
for (j = i - 2; L.elem[0] < L.elem[j]; j--)
{
L.elem[j + 1] = L.elem[j]; //记录后移
}
L.elem[j + 1] = L.elem[0]; //插入到正确位置
}
}
}
希尔排序
- 数据类型定义
typedef int ElemType;
typedef struct
{
ElemType *elem; //顺序表基址，elem[0]闲置或作为监视哨
int length; //顺序表长度
} SqList;
- 算法实现
/**
* 一趟希尔插入排序
*/
void shellInsert(SqList &L, int dk)
{
int i, j;
for (i = dk + 1; i <= L.length; i++)
{
if (L.elem[i] < L.elem[i - dk])
{
L.elem[0] = L.elem[i];
//条件j>0不能省，因为插入的步长为dk，L.elem[0]无法再充当哨兵
for (j = i - dk; j > 0 && L.elem[0] < L.elem[j]; j -= dk)
{
L.elem[j + dk] = L.elem[j]; //记录后移
}
L.elem[j + dk] = L.elem[0]; //插入到正确位置
}
}
}
/**
* 希尔排序
*/
void shellSort(SqList &L, int dlta[], int t)
{
int k;
//按增量dlta[0..t-1]对顺序表L进行希尔插入排序
for (k = 0; k < t; k++)
{
shellInsert(L, dlta[k]);
}
}
快速排序
- 算法实现（版本一）
/**
* 划分算法
*/
int Partition(int rcd[], int low, int high)
{
int pivot = rcd[low]; //记录枢纽关键字
while (low < high) //从 low 和 high 两端交替向中间移动
{
while (low < high && rcd[high] >= pivot)
high--;
rcd[low] = rcd[high]; //比枢纽关键字小的关键字移到低端
while (low < high && rcd[low] <= pivot)
low++;
rcd[high] = rcd[low]; //比枢纽关键字大的关键字移到高端
}
rcd[low] = pivot; //枢纽移到正确位置
return low; //返回枢纽位置
}
/**
* 快速排序（版本一）
*/
void QuickSort(int rcd[], int low, int high)
{
int pivotloc; //枢纽位序
if (low < high)
{
pivotloc = Partition(rcd, low, high);
QuickSort(rcd, low, pivotloc - 1); //对枢纽之前的子序列递归快排
QuickSort(rcd, pivotloc + 1, high); //对枢纽之后的子序列递归快排
}
}
- 算法实现（版本二）
/**
* 快速排序（版本二）
*/
void quick_sort(int rcd[], int low, int high){
if(low >= high){ //递归结束条件
return;
}
int pivot = rcd[low];
int left = low;
int right = high;
while (low < high){
while (low < high && rcd[high] >= pivot)
high--;
rcd[low] = rcd[high];
while (low < high && rcd[low] <= pivot)
low++;
rcd[high] = rcd[low];
}
rcd[low] = pivot;
quick_sort(rcd, left, low-1); //对枢纽之前的子序列递归快排
quick_sort(rcd, high+1, right); //对枢纽之后的子序列递归快排
}
归并排序
- 算法实现（版本一）
/**
* 2-路归并
*/
void Merge(int SR[], int TR[], int i, int m, int n){
//将相邻的有序序列SR[i..m]和SR[m+1..n]归并为有序的TR[i,n]
int k, j;
for (k = i, j = m + 1; i <= m && j <= n; k++){
//将SR中关键字从小到大复制到TR中
if (SR[i] <= SR[j]){
TR[k] = SR[i++];
}else{
TR[k] = SR[j++];
}
}
while (i <= m) //将剩余的SR[i..m]复制到TR
TR[k++] = SR[i++];
while(j <= n) //将剩余的SR[j..n]复制到TR
TR[k++] = SR[j++];
}
/**
* 归并排序（版本一）
*/
void MergeSort(int R1[], int R2[], int i, int low, int high){
//对R1[s..t]归并排序，若i%2==1，则排序后的记录存入R2[s..t]，否则存入R1[s..t]
int mid;
if(low == high){ //结束拆分，准备归并
if(i%2 == 1){
R2[low] = R1[low]; //为保证最后一趟归并到 R1 数组
}
}else{
mid = (low + high) / 2; //将区间[s..t]平分为[s..mid]和[mid..t]
MergeSort(R1, R2, i+1, low, mid); //对区间[s..mid]递归
MergeSort(R1, R2, i+1, mid+1, high); //对区间[mid..t]递归
if(i%2 == 1){
Merge(R1, R2, low, mid, high); //将R1[s..mid]和R1[mid+1..t]归并到R2[s..t]
}else{
Merge(R2, R1, low, mid, high); //将R2[s..mid]和R2[mid+1..t]归并到R1[s..t]
}
}
}
- 算法实现（版本二）
/**
* 归并排序（版本二）
*/
void merge_sort(int SR[], int TR[], int low, int high){
int i, j, k;
if(low >= high){ //直到有序（即只剩一个数）
return;
}
int mid = (low + high) / 2;
merge_sort(SR, TR, low, mid);
merge_sort(SR, TR, mid+1, high);
//将相邻的有序序列SR[i..m]和SR[m+1..n]归并为有序的TR[i,n]
for(k=low, i=low, j=mid+1; i<=mid && j<=high; k++){
if(SR[i] <= SR[j]){
TR[k] = SR[i++];
}else{
TR[k] = SR[j++];
}
}
while(i <= mid)
TR[k++] = SR[i++];
while(j <= high)
TR[k++] = SR[j++];
for(k=low; k<=high; k++){
SR[k] = TR[k]; //复制回待排数组
}
}
查找算法
折半查找
- 算法实现（递归版）
int BinSearch(int rcd[], int key, int low, int high){
//在有序序列rcd[low..high]中折半查找目标关键字key
int mid = (low + high) / 2;
if(low > high)
return -1; //找不到key，返回-1
if(rcd[mid] == key)
return mid; //中间关键字与目标关键字匹配，返回中间关键字下标
else if(rcd[mid] > key)
return BinSearch(rcd, key, low, mid-1); //在前半区折半查找
else
return BinSearch(rcd, key, mid+1, high); //在后半区折半查找
}
- 算法实现（非递归版）
int bin_search(int rcd[], int key, int low, int high){
//在有序序列rcd[low..high]中折半查找目标关键字key
int mid;
while(low <= high){
mid = (low + high) / 2;
if(rcd[mid] == key)
return mid;
else if(rcd[mid] > key)
high = mid - 1; //在前半区折半查找
else
low = mid + 1; //在后半区折半查找
}
return -1; //找不到key，返回-1
}