排序算法----常见的排序算法
2017-12-14 本文已影响0人
Bury丶冬天
算法分类
各算法特性
1.冒泡排序
void bubbleSort(int a[], int length) {
int temp;
for (int i = 0; i < length - 1; ++i) {
for (int j = 0; j < length - 1 - i; ++j) {
if (a[j] > a[j + 1]) {
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}
2.简单选择排序
void selectionSort(int a[], int length) {
int temp, minIndex;
for (int i = 0; i < length - 1; ++i) {
//假设 a[i] 是当前最小值
minIndex = i;
//找数组后面是否还有 比 min更小的数
for (int j = i + 1; j < length; ++j) {
//如果 当前考察位置(a[j]) 小于 a[minIndex] 则更新 索引
if (a[j] < a[minIndex]) {
//更新索引
minIndex = j;
}
}
//交换
if (minIndex != i) {
temp = a[i];
a[i] = a[minIndex];
a[minIndex] = temp;
}
}
}
3.直接插入排序
/**
* 经典插入排序
* @param arr
* @param length
*/
void insertionSort(int *arr, int length) {
int temp;
for (int i = 1; i < length; ++i) {
for (int j = i; j > 0 && arr[j - 1] > arr[j]; --j) {
temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
}
}
}
/**
* 优化的插入排序
* @param arr
* @param length
*/
void insertionSort1(int *arr, int length) {
for (int i = 1; i < length; ++i) {
int e = arr[i], j;
for (j = i; j > 0 && arr[j - 1] > e; --j) {
arr[j] = arr[j - 1];
}
arr[j] = e;
}
}
