稳定:如果 a 原本在 b 前面,而 a =b,排序之后 a 仍然在 b 的前面;
不稳定:如果 a 原本在 b 的前面,而 a =b,排序之后 a 可能会出现在 b 的后面;
内排序:所有排序操作都在内存中完成;
外排序:由于数据太大,因此把数据放在磁盘中,而排序通过磁盘和内存的数据传输才能进行;
时间复杂度:一个算法执行所耗费的时间。
空间复杂度:运行完一个程序所需内存的大小。
排序
int a[] = {10,9,8,7,6,5,4,3,2,1};
int count = sizeof(a)/sizeof(int);
选择排序
for (int i = 0; i < count; i++) {
int minIndex = i;// 从第一个位置开始
for (int j =i+1 ; j <count; j++) {if (a[minIndex] > a[j]) {minIndex = j; // 找到剩余数中最小数的索引}
}
// 交换
int temp = a[i];
a[i] = a[minIndex];
a[minIndex] = temp;
}
冒泡排序
for (int i = 0; i < count; i++) {for (int j = 0; j < count-1-i; j++) {if (a[j]>a[j+1]) {int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
快速排序
void swap(int arr[], int low, int high) {if (low == high) {return;}
int temp;
temp = arr[low];
arr[low] = arr[high];
arr[high] = temp;
}
int findPartition(int arr[], int low, int high){int base = arr[low];
while (low<high) {while (low<high && arr[high]>=base) {high--;}
swap(arr, low, high);
while (low<high && arr[low]<=base) {low++;}
swap(arr, low, high);
}
return low;
}
void QS(int arr[], int low, int high) {if (low<high) {int base = findPartition(arr,low,high);
QS(arr, low, base-1);
QS(arr, base+1, high);
}
}