冒泡排序
- 决定冒泡的方向，每次冒泡相邻元素比较，每次固定一个泡。
- 如果一趟未产生任何交换，则整个序列已排序，无需再比较。
- 时间复杂度：比较的次数n-1 … 1 , 总和 O(n^2) , 空间复杂度 O(1)
int a[100] = {1, 2, 10, 3, 5, 4, 2};
void swap(int i, int j) {
if (i != j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}
//冒泡排序, 从小到大
void bubbleSort(int a[], int n) {
if (n <= 1) {
return;
}
for (int i = 0; i < n - 1; i++) { //每次要确定的冒泡元素
int sorted = 1; //做一个优化，如果一趟排序中都没有产生交换，则不需要以后操作
for (int j = n - 1; j > i; j--) { //从后往前冒
if (a[j] < a[j - 1]) {
swap(j, j-1);
sorted = 0;
}
}
if (sorted == 1) {
break;
}
}
}
快速排序
- 快排核心找基准数，把基准数放到某一个位置，左边的都比它小，右边的都比它大。
- 如果我们以最左边的为基准，那么需要注意的是为什么从右边找，因为从左边找，你可能无法找到比它小的元素，这样你就无法执行基准数和找到的数的交换，如果从右边找，至少可以找到刚好等于基准数的元素，这样才满足基准数左边都小于，右边都大于的思想。
- 时间复杂度：如果每次被二分，总共被分成的是logn 趟， 每次比较的是 n 次， 时间复杂度 O(nlogn), 空间复杂度 O(1) 。
void quickSortByRange(int a[], int left, int right){
if (left >= right) {
return;
}
int l = left;
int r = right;
int pivotIndex = left;
int pivot = a[left];
//基准数在左边，为什么是从右边找，而不是从左边找呢，因为如果从左边找，你很可能找不到，这样就无法执行
//基准数和相遇点的交换了，而从左边找，至少可以直接找到基准数的这个位置
while (left < right) {
while (left < right && a[right] >= pivot) { //从右边找到比基准数小的那个
right--;
}
while (left < right && a[left] <= pivot) {
left++;
}
if (left < right) {
swap(left, right);
}
}
if (left <= right) { //在不出现越界的情况下，执行基准和相遇点的交换
swap(pivotIndex, left);
quickSortByRange(a, l, left - 1);
quickSortByRange(a, left + 1, r);
}
}
void quickSort(int a[], int n) {
if (n <= 1) {
return;
}
quickSortByRange(a, 0, n - 1);
}
插入排序
- 插入排序关键在于插入，分割为排序和未排序部分，不断把右边的元素插入到左边的序列中，注意是相邻元素交换。
- 时间复杂度：O(n^2), 空间复杂度 O(1)
void insertOrder(int array[], int n) {
if (n <= 1) {
return;
}
//每次选定一个元素同前面的已排序的元素做对比，找到应该插入的位置
for (int i = 1; i < n; i++) {
int key = array[i];
int j = i - 1;
while (j >= 0) {
if (key > array[j]) {
swap(array, j, j+1);
}
else {
break;
}
j--;
}
}
}
选择排序
- 选择排序每次从未排序的队列中选择出最大或者最小元素，放到已排序的队列末尾。
- 时间复杂度: O(n^2) , 空间复杂度: O(1)
///选择排序,降序,
void selectOrder(int array[], int n) {
if (n <= 1) {
return;
}
//选择排序，每次从无序的被选的元素中找最大或者最小的放到有序的环境中
for (int i = 0; i < n; i++){
int selectIndex = i;
for (int j = i + 1; j < n; j++) {
if (array[j] > array[i]) {
selectIndex = j;
}
}
swap(array, i, selectIndex);
}
}
}
其他
- 因为快排拥有比较好的平均时间复杂度，所以快排用的范围相对来说更广一些。
