Пузырьковая сортировка так же проста
Я познакомился с пузырьковой сортировкой (в то время написанной на C), когда изучал C и структуры данных на первом курсе. Теперь, когда я джуниор, я хочу найти стажировку на летних каникулах, и мне нужно проверить знания структур данных и алгоритмов.
Рейтинг нам не чужд: когда вы играете в King's Glory, будут очки ранга, а когда вы играете в Dota, будут очки рейтинга. Считая сверху вниз, это ранжирование является регулярным, т. е. своеобразным.
Мой первый контакт с пузырьковой сортировкой, поэтому этот пост в блоге в основном посвящен пузырьковой сортировке.
Реализация пузырьковой сортировки
Источник Энциклопедия Baidu:
Пузырьковая сортировка (Bubble Sort, Тайвань переводится как: пузырьковая сортировка или пузырьковая сортировка) — простой алгоритм сортировки. Он неоднократно проходит через последовательность для сортировки, сравнивая два элемента за раз и меняя их местами, если они находятся в неправильном порядке. Работа по посещению последовательности повторяется до тех пор, пока перестановки не понадобятся, то есть последовательность отсортирована. Название этого алгоритма происходит от того факта, что более крупные элементы будут медленно «плавать» в верхней части последовательности путем замены местами, отсюда и название.
Описание алгоритма:
iначиная с 0,iиi+1сравнить, еслиi>i+1, затем поменять местамиiувеличивая доi<n-1(n — количество элементов массива,n-1является последним элементом массива), один проход вниз, вы можете сделать максимальное значение в элементе массива в конце массива
Начнем с самого простого, сначала создадим массив из 5 цифр:
int[] arrays = {2, 5, 1, 3, 4};
Во-первых, первый заказ
Далее проведем проверку кода по описанию алгоритма** (первая сортировка)**:
//使用临时变量，让两个数互换
int temp;
//第一位和第二位比
if (arrays[0] > arrays[1]) {
//交换
temp = arrays[0];
arrays[0] = arrays[1];
arrays[1] = temp;
}
//第二位和第三位比
if (arrays[1] > arrays[2]) {
temp = arrays[1];
arrays[1] = arrays[2];
arrays[2] = temp;
}
//第三位和第四位比
if (arrays[2] > arrays[3]) {
temp = arrays[2];
arrays[2] = arrays[3];
arrays[3] = temp;
}
//第四位和第五位比
if (arrays[3] > arrays[4]) {
temp = arrays[3];
arrays[3] = arrays[4];
arrays[4] = temp;
}
Если предыдущая цифра больше следующей, то меняем местами до тех пор, пока не будут сравнены все элементы массива!
После нашего первого сравнения, мы можем узнать:Самое большое значение находится в конце массива!
Первый, второй заказ
Второй сортировку совпадает с первым сопоставлением, но и предыдущий и последний, если предыдущий является больше, то обменять. Стоит отметить, что:Его не нужно сравнивать с последним, потому что в первой сортировке последнее уже является самым большим числом.. Так же,После второго раунда сортировки предпоследнее число также является вторым по величине числом.
Код для второй сортировки выглядит следующим образом:
//第一位和第二位比
if (arrays[0] > arrays[1]) {
//交换
temp = arrays[0];
arrays[0] = arrays[1];
arrays[1] = temp;
}
//第二位和第三位比
if (arrays[1] > arrays[2]) {
temp = arrays[1];
arrays[1] = arrays[2];
arrays[2] = temp;
}
//第三位和第四位比
if (arrays[2] > arrays[3]) {
temp = arrays[2];
arrays[2] = arrays[3];
arrays[3] = temp;
}
//第四位不需要和第五位比了，因为在第一趟排序结束后，第五位是最大的了。
результат:Наше второе по величине число уже предпоследнее
Три, упрощение кода
Стоит отметить, что: приведенные выше результатывыглядитОн уже отсортирован, но данные недостаточно беспорядочны, когда я его тестирую.Если данные достаточно беспорядочны, сортировка занимает 4(n-1) раз.!
Но мы можем найти из приведенного выше кода:Коды сравнения и обмена первого и второго раундов повторяются, и все наши сравнения жестко закодированы (0,1,2,3,4), что не является универсальным!
В нашем массиве 5 цифр
- Первую поездку нужно сравнивать4 раза
- Вторую поездку нужно сравнивать3 раза
Мы можем сделать вывод из приведенных выше правил:
- Третью поездку нужно сравнивать2 раза
- Четвертую ложь нужно сравнить1 раз
Из приведенных выше правил можно сделать вывод, что:5-значный массив нужно отсортировать по 4 ставкам, причем количество раз после каждой кладки уменьшать на 1 (т.к. предыдущая поездка уже определила максимальное значение предыдущей поездки)!
Так что мы можемУпростите приведенный выше код на основе цикла for и переменных.:
int temp;
//外层循环是排序的趟数
for (int i = 0; i < arrays.length - 1 ; i++) {
//内层循环是当前趟数需要比较的次数
for (int j = 0; j < arrays.length - i - 1; j++) {
//前一位与后一位与前一位比较，如果前一位比后一位要大，那么交换
if (arrays[j] > arrays[j + 1]) {
temp = arrays[j];
arrays[j] = arrays[j + 1];
arrays[j + 1] = temp;
}
}
}
В-четвертых, оптимизация пузырьковой сортировки
Из приведенного выше примера видно, что если данные достаточно беспорядочны, массив необходимо полностью отсортировать после 4 сравнений.Но уже после второго сравнения мы получаем отсортированный массив.
Однако наша программа по-прежнему будет выполнять сортировку третьего и четвертого прохода после второго прохода сортировки. Это не нужно, поэтому мы можем немного оптимизировать его:
-
Если при определенном сортировании не происходит подкачки, то можно считать, что массив отсортирован..
- Это нетрудно понять, потому что мыЦелью каждой сортировки является замена наибольшего числа текущего раунда на соответствующую позицию, причем сортировка производилась без описания замены.
код показывает, как показано ниже:
//装载临时变量
int temp;
//记录是否发生了置换， 0 表示没有发生置换、 1 表示发生了置换
int isChange;
//外层循环是排序的趟数
for (int i = 0; i < arrays.length - 1; i++) {
//每比较一趟就重新初始化为0
isChange = 0;
//内层循环是当前趟数需要比较的次数
for (int j = 0; j < arrays.length - i - 1; j++) {
//前一位与后一位与前一位比较，如果前一位比后一位要大，那么交换
if (arrays[j] > arrays[j + 1]) {
temp = arrays[j];
arrays[j] = arrays[j + 1];
arrays[j + 1] = temp;
//如果进到这里面了，说明发生置换了
isChange = 1;
}
}
//如果比较完一趟没有发生置换，那么说明已经排好序了，不需要再执行下去了
if (isChange == 0) {
break;
}
}
5. Расширенное чтение
Язык C реализует первый способ:
void bubble ( int arr[], int n)
{
int i;
int temp;
for (i = 0; i < n - 1; i++) {
if (arr[i] > arr[i + 1]) {
temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
}
void bubbleSort ( int arr[], int n)
{
int i;
for (i = n; i >= 1; i--) {
bubble(arr, i);
}
}
Язык C реализует второй способ рекурсии:
void bubble ( int arr[], int L, int R)
{
if (L == R) ;
else {
int i;
for (i = L; i <= R - 1; i++)//i只能到达R-1
if (arr[i] > arr[i + 1]) {
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
bubble(arr, L, R - 1);//第一轮已排好R
}
}
Тестовый код:
int main ()
{
int arr[] = {2, 3, 4, 511, 66, 777, 444, 555, 9999};
bubbleSort(arr, 8);
for (int i = 0; i < 9; i++)
cout << arr[i] << endl;
return 0;
}
5.1 Понимание временной сложности:
Если в статье есть какие-либо ошибки, пожалуйста, поправьте меня, и мы сможем общаться друг с другом. Учащиеся, привыкшие читать технические статьи в WeChat и желающие получить больше ресурсов по Java, могутОбратите внимание на публичный аккаунт WeChat: Java3y