Эффективность сортировки обычно сравнивают по трем аспектам: количеству сравнений данных, количеству перемещений данных и объему занимаемой памяти.
Давайте проведем общее сравнение пузырьковой сортировки, сортировки выбором, сортировки вставками и быстрой сортировки. Алгоритм пузырьковой сортировки обычно не используется, поскольку его количество сравнений и ходов является самым большим среди нескольких алгоритмов сортировки. Его единственное преимущество заключается в том, что алгоритм прост и понятен, поэтому его можно использовать, когда объем данных невелик. будет некоторая прикладная ценность. Сортировка выбором имеет такое же количество сравнений, как и пузырьковая сортировка, которая равна n в квадрате, но она уменьшает количество обменов до минимума, поэтому ее можно применять, когда объем данных невелик и обмен данными требует больше времени, чем сравнение. данные. Выберите сортировку.
В большинстве случаев, когда объем данных относительно невелик или в основном упорядочен, алгоритм сортировки вставками является лучшим выбором. Для сортировки больших объемов данных обычно лучшим методом является быстрая сортировка.
Вышеописанный алгоритм сортировки занимает очень мало места в памяти и требует лишь дополнительной переменной для временного хранения элементов данных во время обмена. Поэтому нет никакого сравнения по размеру занимаемого пространства памяти.
Число сравнений сортировки вставками по-прежнему равно n в квадрате, но в целом она в два раза быстрее, чем сортировка пузырьком, и немного быстрее, чем сортировка выбором. Он часто используется на заключительных этапах сложных алгоритмов сортировки, таких как быстрая сортировка.
Алгоритм: После обработки i-1 L[1..i-1] отсортирован. i-й проход вставляет только L[i] в соответствующую позицию L[1..i-1],
Итак, L[1..i] снова является упорядоченной последовательностью. Для достижения этой цели мы можем использовать последовательное сравнение.
Сначала сравните L[i] и L[i-1]. Если L[i-1]<=L[i], то L[1..i] отсортирован и i-й проход обработки завершен;
В противном случае поменяйте местами позиции L[i] и L[i-1] и продолжайте сравнивать L[i-1] и L[i-2] до тех пор, пока не будет найдена определенная позиция j (1≤j≤i-1). найденный.
Пока L[j] ≤L[j+1]
Преимущества: перемещается меньше элементов и требуется только вспомогательное пространство.
Временная сложность n*n
Это хороший метод сортировки, когда число n сортируемых записей невелико. Но когда n очень велико, это нецелесообразно.
Например: значения int[] = { 5, 2, 4, 1, 3 };
Процесс сортировки:
1-й раз: 2,5,4,1,3
2-й раз: 2,4,5,1,3
3-й раз: 1,2,4,5,3
4-й раз: 1,2,3,4,5
Java-код:
Скопируйте код кода следующим образом:
общественный класс InsertSort {
public static void main(String[] args) {
значения int[] = { 5, 2, 4, 1, 3 };
сортировка (значения);
for (int i = 0; i <values.length; ++i) {
System.out.println(значения[i]);
}
}
общественная статическая недействительная сортировка (значения int []) {
внутренняя температура;
интервал j = 0;
for (int i = 1; i <values.length; i++) {
if(values[i]<values[i-1])//Это решение очень важно. Оно отражает причину, по которой сортировка вставкой выполняется быстрее, чем сортировка пузырьком и сортировка выбором.
{
температура = значения [я];
//Перемещаем данные назад
for (j=i-1; j>=0 && temp<values[j]; j--)
{
значения[j+1] =значения[j];
}
//Вставляем данные в позицию j+1
значения [j+1] = temp;
System.out.print("th" + (i + 1) + "th:");
for (int k = 0; k <values.length; k++) {
System.out.print(values[k]+",");
}
System.out.println("");
}
}
}
}
Второй пример
Скопируйте код кода следующим образом:
пакет cn.cqu.coce.xutao;
общественный класс жижиечару {
public static void main(String args[]){
int a[]={1,2,34,67,8,9,6,7,56,34,232,99};
интервал я, j, к;
for(i=0;i<a.length;i++)
System.out.print(a[i]+"/t");
Система.out.println();
for(i=1;i<a.length;i++){
for(j=i-1;j>=0;j--)
если(а[i]>a[j])
перерыв;
если(j!=i-1){
внутренняя температура;
темп = а [я];
for(k=i-1;k>j;k--)
а[к+1]=а[к];
а[к+1]=температура;
}
}
for(i=0;i<a.length;i++)
System.out.print(a[i]+"/t");
Система.out.println();
}
}