1. 插入排序
直接插入排序
在要排序的一组数中,假设前n-1个数已经拍好顺序,现将第n个数插到有序数列中,使这n个数也是排序好的,如此循环,直到全部排好顺序。O(n^2)
代码实现:
void InsertSort(int array[],int length){
int temp;
for(int i = 0;i < length - 1;i++){
for(int j = i+1;j > 0;j++){
if(array[j] < array[j-1]){
temp = array[j-1];
array[j-1] = array[j];
array[j] = temp;
}else{
`break;
}
}
}
}
希尔排序
2. 选择排序
简单排序
堆排序
3. 交换排序
冒泡
两个数比较大小,较大的书下沉,较小的数冒出。
过程:比较相邻数据,若第二个数小,就交换位置:从后向前两两比较,一直到比较最前两个数据最终最小数据被交换到起始位置,则第一个最小数位置排好:重复上述过程,将剩余数排好。
代码实现:
void BubbleSort(int arr[]){
int temp;
for(int i = 0;i < arr.length-1;i++){
for(int j=arr.length-1;j>i;j--){
if(arr[j]<arr[j-1]){
temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
}
}
}
}
优化:多数时候,数据排好顺序后,算法仍会进行下一轮比较,知道arr.length-1次,后面的比较无意义。此时可设置标志位flag,用于标志某一趟排序过程是否有数据交换,若未发生交换,则可立即结束排序。
void BubbleSort(int arr[]){
int temp;
for(int i = 0;i < arr.length-1;i++){
bool flag = false;
for(int j=arr.length-1;j>i;j--){
if(arr[j]<arr[j-1]){
temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
flag = true;
}
}
if(!flag)
break;
}
}
网友评论