冒泡算法
将元素进行两两比较,将大的元素往后移动
平均时间复杂度是O(n^2),最坏时间复杂度是O(n^2),最好时间复杂度是O(n),排序结果具有稳定性。
这里所提到的稳定性主要是针对相同元素而言的,比如5,5,3进行冒泡排序,第一个5始终在第二个5的前面,这两个5的顺序不会发生变化。
void bubblesort(int arr[], int n)
{for (int i = 0; i < n - 1; i++){bool finished = true;for (int j = 0; j < n - 1-i; j++){if (arr[j] > arr[j + 1]){swap(arr[j], arr[j + 1]);finished = false;}}if (finished)return;//如果finished为true就代表没有元素发生交换,也就是说所有元素都已经有序了}
}
选择排序算法
假设队首元素为最小值,然后遍历后续的元素找到真正的最小值,并与队首进行交换,每次在剩余元素中选择最小的元素与当前元素进行交换。
平均时间复杂度是O(n^2),最好时间复杂度是O(n^2),最坏时间复杂度是O(n^2),排序结果不稳定。
假如有一个5,5,3的序列,那么当使用选择排序进行排序时,第一个5就和最后的一个3进行交换了,但实际上第一个5是在第二个5的前面的,但是排完序后,第一个5到第二个5后面去了,所以是不稳定的。
void choicesort(int arr[], int n)
{for (int i = 0; i < n; i++){int min_element = arr[i];int min_index = i;for (int j = i; j < n; j++){if (arr[j] < min_element){min_element = arr[j];min_index = j;}}swap(arr[i], arr[min_index]);}
}