В последнее время я чувствую, что мое программирование не продвигается, и я хочу практиковать свои внутренние навыки, поэтому я начал просматривать и изучать структуры данных и алгоритмы. На самом деле программисты, вероятно, знают поговорку «программа равна алгоритму + структуре данных», понимание и выбор подходящих структур данных и алгоритмов являются предпосылками для написания отличных программ. В JAVA JDK вы также можете подсмотреть важность алгоритмов структуры данных, например, массив + связанный список используется в HashMap для повышения эффективности поиска и вставки. Я также хочу повысить эффективность своего обучения, подытоживая и пишу статьи, поэтому у меня есть эта статья. Чтобы заставить себя, я решил в будущем каждую неделю писать в блог (не обязательно все о структурах данных и алгоритмах). Из-за моего ограниченного уровня и слабого литературного таланта я редко пишу блоги, надеюсь, что большие ребята, которые увидят статью, смогут высказать свое мнение и предложения.
1. Пузырьковая сортировка
1. Описание
Пузырьковая сортировка, сравнивайте размер двух соседних чисел каждый раз, когда пузырьки, если отношение размера не правильное, то обменивайте. Как показано на рисунке ниже, первая ложь всплывает вниз, самое большое значение будет размещено в правильной позиции, и в правильной позиции могут быть другие числа. Таким образом, за один спуск по крайней мере один из самых больших находится в правильном положении (9 на рисунке ниже).
После второго прохода среди оставшихся чисел после первого прохода самая большая 8 снова окажется в правильном положении (как показано на рисунке ниже).
Это будет всплывать до n-1 раз, и это будет упорядоченная последовательность
2. Код JAVA реализован следующим образом
//时间复杂度为O(n^2) 最好时间复杂度O(n) 平均时间复杂度O(n^2)
public static void sort(int numArray[]) {
if (numArray == null || numArray.length == 0) {
return;
}
int arrayLength = numArray.length;
int tmp;
//这一趟是否有发生交换，如果没有发生交换，说明数组已经是有序的，不需要再冒泡了。
boolean flag = false;
//外层：需要length-1次循环比较，需要做n-1次冒泡
for(int i= 0; i < arrayLength - 1; i++) {
flag = false;
for(int j=0; j < arrayLength -i-1; j++) {
//内层：每次循环需要两两比较的次数，每次比较后，都会将当前最大的数放到最后位置
if(numArray[j] > numArray[j+1]) {
tmp = numArray[j];
numArray[j] = numArray[j+1];
numArray[j+1] = tmp;
flag = true;
}
}
if(!flag) //没有任何交换，数组已经处于有序
break;
}
}
Во-вторых, сортировка выбором
1. Описание
Сортировка выбором показана на рисунке ниже.Каждый раз найдите наименьшее значение среди оставшихся и поместите наименьшее значение в правильное положение.
2,Код JAVA реализован следующим образом
public static void selectSort(int numArray[]) {
int length = numArray.length;
int min,pos;
//每一次循环都会找出剩下中的最小数，放到正确的位置
for(int i= 0; i < length-1; i++) {
min = numArray[i];
pos = i;
//找出剩余中的最小数
for(int j = i+1; j < length; j++) {
if(numArray[j] < min) {
min = numArray[j];
pos = j;
}
}
if(pos != i) {
numArray[pos] = numArray[i];
numArray[i] = min;
}
}
}3. Сортировка вставками
1. Описание
Сортировка вставками аналогична сортировке карт при игре в покер: каждый раз, когда вытягивается карта, она вставляется в уже заказанные карты в руке. В приведенном ниже примере мы начинаем со второго числа и вставляем его впереди. Как показано на рисунке ниже, во второй раз 6 нужно вставить между передними 5 и 8, поэтому переместите 8 назад, а затем вставьте 6.
2,Код JAVA реализован следующим образом
public static void insertSort(int intList[]) {
int j = 1;
int i;
for(; j < intList.length; j++) {
i = j-1;
int key = intList[j];
while(i > -1 && intList[i] > key) {
intList[i+1] = intList[i];
i--;
}
intList[i+1] = key;
}
//时间复制度为O(n^2) ,最好情况时间复杂度O(n),平均时间复杂度O(n^2)
}4. Быстрая сортировка
1. Описание
Быстрая сортировка использует идею «разделяй и властвуй».Общая идея состоит в том, чтобы выбрать число в качестве эталонного значения и поместить перед ним все элементы, меньшие, чем оно, а элементы, большие, чем оно, помещаются за ним, а затем опорное значение находится в правильном положении, отсортируйте два массива до и после опорного значения, и они будут отсортированы в конце. Есть много способов реализовать быструю сортировку, следующие реализованы с помощью левого и правого указателей.
2,Код JAVA реализован следующим образом
public static void quickSort(int numArray[],int _left, int _right) {
int left = _left;
int right = _right;
int temp = 0;
if(left <= right){ //待排序的元素至少有两个的情况
temp = numArray[left]; //待排序的第一个元素作为基准元素
while(left != right){ //从左右两边交替扫描，直到left = right
while(right > left && numArray[right] >= temp)
right --; //从右往左扫描，找到第一个比基准元素小的元素
numArray[left] = numArray[right]; //找到这种元素arr[right]后与arr[left]交换
while(left < right && numArray[left] <= temp)
left ++; //从左往右扫描，找到第一个比基准元素大的元素
numArray[right] = numArray[left]; //找到这种元素arr[left]后，与arr[right]交换
}
numArray[right] = temp; //基准元素归位
quickSort(numArray,_left,left-1); //对基准元素左边的元素进行递归排序
quickSort(numArray, right+1,_right); //对基准元素右边的进行递归排序
}
}Пять, сортировка слиянием
1. Описание
Сортировка слиянием также является идеей «разделяй и властвуй».Во-первых, все элементы разделяются и сортируются постепенно.Принцип заключается в следующем.
2,Код JAVA реализован следующим образом
public static int[] sort(int [] a) {
if (a.length <= 1) {
return a;
}
int num = a.length >> 1;
int[] left = Arrays.copyOfRange(a, 0, num);
int[] right = Arrays.copyOfRange(a, num, a.length);
return mergeTwoArray(sort(left), sort(right));
}
public static int[] mergeTwoArray(int[] a, int[] b) {
int i = 0, j = 0, k = 0;
int[] result = new int[a.length + b.length]; // 申请额外空间保存归并之后数据
while (i < a.length && j < b.length) { //选取两个序列中的较小值放入新数组
if (a[i] <= b[j]) {
result[k++] = a[i++];
} else {
result[k++] = b[j++];
}
}
while (i < a.length) { //序列a中多余的元素移入新数组
result[k++] = a[i++];
}
while (j < b.length) {//序列b中多余的元素移入新数组
result[k++] = b[j++];
}
System.out.println(Arrays.toString(result));
return result;
}