选择排序
选择排序应该是最容易被想到的排序方式吧
1.从头开始,与自己的后一位比较,如果小的就交换值
2.外层循环执行 n-1 次即可
- 平均时间复杂度:O(n²)
- 最好情况复杂度:O(n²)
- 最坏情况复杂度:O(n²)
void selectSort(int *arr, int count){
for (int i = 0; i < count -1; i++){ // count - 1 次即可完成排序
for(int j = i+1; j < count; j++){ // 从 i 位置 逐个与 后面的元素进行比较
if(arr[i] >= arr[j]) continue;
arr[i] = arr[i] + arr[j]; // 交换
arr[j] = arr[i] - arr[j];
arr[i] = arr[i] - arr[j];
}
}
}
冒泡排序
1.从头开始相邻两个元素两两比较,a[i] > a[i+1] 交换则交换两者位置
2.每循环一次,即可确定一位
- 平均时间复杂度:O(n²)
- 最好情况复杂度: O(n)
- 最坏情况复杂度:O(n²)
void bubbleSort(int *arr, int count){
for(int i = 0; i < count; i++){
for(int j = 0; j < count - 1 - i; j++){
if (arr[j] < arr[j+1]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
插入排序
貌似扑克牌整理顺序
1.从头开始,逐个跟前一个元素对比
2.如果比前一个元素小,即交换两个元素的位置,交换的次数比较多
- 平均时间复杂度:O(n²)
- 最好情况复杂度:O(n)
- 最坏情况复杂度: O(n²)
void insertSort(int *arr,int count){
for(int i = 0; i < count; i++){ // 一共循环的次数
for(int j = i; j>0;j--){ //从当前 i 的位置与前一个对比
if(arr[j] < arr[j-1]){ // 如果后者小于前者,则交换,否则结束当前循环进入下一次。
int temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
}else{
break;
}
}
}
归并排序
所谓 归并 是指将若干个已排好序的部分合并成一个有序的部分。
- 平均时间复杂度:O( n log n)
- 最好情况复杂度:O( n log n)
- 最差情况复杂度:O( n log n)
void mergeSort(int *total, int *arr_A, int length_A, int *arr_B, int length_B){
int i = 0;
int j = 0;
while( i < length_A && j < length_B){
if( arr_A[i] < arr_B[j] ){
total[ i + j ] = arr_A[i++];
}else{
total[ i+j ] = arr_B[j++];
}
while(i<length_A){
total[ i+j ] = arr_A[i];
i++;
}
while(j < length_B){
total [ i + j ] = arr_B[j];
j++;
}
}
快速排序
快排是现有排序算法中最快的
1.选择一个值,将数组中比该值大的都放到该值右侧,小的都放到左侧
2.以该值的位置将数组分割成左右两个部分,分别对左右两个部分执行上一步操作
- 平均时间复杂度:O(n log n)
- 最好情况复杂度: O(n log n)
- 最坏情况复杂度: O(n²)
void quickSort(int *arr, int leftIndex, int rightIndex){
if (leftIndex >= rightIndex) return;
int kp = keyPoint(arr,leftIndex,rightIndex);
quickSort(leftIndex,kp-1);
quickSort(kp+1,rightIndex);
}
int keyPoint(int *arr, int leftIndex,int rightIndex){
int l = leftIndex;
int r = rightIndex;
int key = arr[i];
while(l < r){
while( l < r && arr[r] > key) r--;
if (l < r){
arr[l++] = arr[r];
}
while(l < r && arr[l] < key) l++;
if (l < r){
arr[r--] = arr[l];
}
arr[l] = key;
}
return l;
}
网友评论