предисловие
Алгоритмы — это душа программирования, и программисты, которые не знают, как работать с алгоритмами, годятся только для того, чтобы быть фермерами кода. Я видел это предложение раньше и получил 10 000 критического урона! В то же время это подняло и мой боевой дух.Честно говоря, как программист, я всегда знал о важности алгоритмов, но я не смог добиться достаточного успеха в области алгоритмов, и даже редко прикасаюсь к ней. после прохождения этого курса в колледже. Потому что вначале я обозначил алгоритм как сложный, надоедливый и не очень полезный, а теперь, подумав об этом, я фактически убегаю от проблемы. Поэтому я решил загладить свою вину и начать с нуля!
Статья была впервые опубликована в личном блоге【www.xiongfrblog.cn】
вводить
Обучение алгоритму также имеет этапы: от начального к простому, к сложному, к простому. Конечная простота заключается в том, что при достижении определенной высоты можно безошибочно найти простейший ответ на задачу. Как и при взращивании бессмертных, одного движения настоящего мастера достаточно, чтобы дать отпор тысячам лошадей и тысячам воинов!
Наиболее часто используемые и самые основные алгоритмы - это алгоритм сортировки и алгоритм поиска, В этой статье в основном объясняются десять самых классических алгоритмов сортировки в алгоритме. Здесь мы делим десять лучших алгоритмов сортировки на две категории в соответствии с принципами их реализации и эффективностью:
- Нелинейная сортировка сравнением: Нелинейная означает, что временная сложность алгоритма не может превзойти (nlogn), а порядок элементов определяется путем сравнения размера элементов.
- Линейная несравнительная сортировка: временная сложность алгоритма может пробиваться (nlogn), и элементы сортируются без сравнения.
Конкретная классификация описана на рисунке выше:
Сравнение алгоритмов
Вот сравнение временной сложности, пространственной сложности и устойчивости алгоритма, которое также приведено в виде картинки:
Объяснение соответствующих индикаторов приведено здесь
временная сложность: Временная сложность предназначена для оценки времени выполнения алгоритма, но на самом деле программа выполняется на компьютере очень быстро, а время практически ничтожно, а значит теряет смысл, значит, частота выполнения в алгоритм - Количество исполнений кода высшей степени. Реакция При изменении n какую закономерность показывает изменение числа казней.космическая сложность: относится к объему памяти, необходимому алгоритму для выполнения на компьютере, а также является функцией размера данных n.стабильность: Для двух элементов a, b, которые равны в сортировке. Если a перед b перед сортировкой, a всегда перед b после сортировки. Их положение не меняется из-за упорядочения и называется устойчивым. И наоборот, если позиции a и b могут измениться после сортировки, это называется неустойчивым.
Ниже приводится подробное объяснение десяти лучших алгоритмов один за другим, а также их основные идеи, демонстрации изображений и исходный код с подробными комментариями. (Все алгоритмы сортировки в этой статье расположены в порядке возрастания)
1. Пузырьковая сортировка
1.1 Основная идея
Пузырьковая сортировка, возможно, является одной из самых простых сортировок, и большинство людей думают о ней проще всего. То есть для сортировки n чисел каждый раз предыдущее число сравнивается со следующим числом, и каждый цикл может перемещать наибольшее число в конец массива, а всего выполняется n-1 циклов для завершения сортировки массив. .
1.2 Демонстрация изображения
1.3 Отображение кода
public static void bubbleSort(int[] arr) {
if(arr==null)
return;
int len=arr.length;
//i控制循环次数，长度为len的数组只需要循环len-1次，i的起始值为0所以i<len-1
for(int i=0;i<len-1;i++) {
//j控制比较次数，第i次循环内需要比较len-i次
//但是由于是由arr[j]跟arr[j+1]进行比较，所以为了保证arr[j+1]不越界，j<len-i-1
for(int j=0;j<len-i-1;j++) {
//如果前一个数比后一个数大，则交换位置将大的数往后放。
if(arr[j]>arr[j+1]) {
int temp=arr[j+1];
arr[j+1]=arr[j];
arr[j]=temp;
}
}
}
}
2. Сортировка выбором
2.1 Основная идея
Можно сказать, что сортировка выбором является улучшенной версией пузырьковой сортировки.Вместо сравнения предыдущего числа со следующим числом в каждом цикле число сравнивается со всеми числами, и каждое сравнение выбирается.Относительно небольшое число используется для следующее сравнение, и нижний индекс меньшего числа постоянно обновляется, так что в конце цикла можно получить нижний индекс наименьшего числа, а затем наименьшее число помещается вверху посредством обмена Сортировка выполняется через n-1 пет. Таким образом, по сравнению с пузырьковой сортировкой количество сравнений не изменилось, но количество обменов данными значительно сократилось.
2.2 Демонстрация изображений
2.3 Отображение кода
public static void selectSort(int[] arr) {
if(arr==null)
return;
int len=arr.length;
//i控制循环次数，长度为len的数组只需要循环len-1次，i的起始值为0所以i<len-1
for(int i=0;i<len-1;i++) {
//minIndex 用来保存每次比较后较小数的下标。
int minIndex=i;
//j控制比较次数，因为每次循环结束之后最小的数都已经放在了最前面，
//所以下一次循环的时候就可以跳过这个数，所以j的初始值为i+1而不需要每次循环都从0开始，并且j<len即可
for(int j=i+1;j<len;j++) {
//每比较一次都需要将较小数的下标记录下来
if(arr[minIndex]>arr[j]) {
minIndex=j;
}
}
//当完成一次循环时，就需要将本次循环选取的最小数移动到本次循环开始的位置。
if(minIndex!=i) {
int temp=arr[i];
arr[i]=arr[minIndex];
arr[minIndex]=temp;
}
//打印每次循环结束之后数组的排序状态（方便理解）
System.out.println("第"+(i+1)+"次循环之后效果："+Arrays.toString(arr));
}
}
3. Сортировка вставками
3.1 Основная идея
Идея сортировки вставками, безусловно, проста для понимания игроками в покер, то есть увидеть, где находится игла. Во-первых, положение первого числа в массиве по умолчанию правильное, то есть оно отсортировано. Затем возьмите следующее число и сравните его с уже отсортированными числами в порядке от конца к началу.Если число меньше отсортированного числа в текущей позиции, переместите отсортированное число назад на одну позицию. Повторяйте предыдущий шаг, пока не будет найдено подходящее место. После того, как позиция найдена, цикл сравнения завершается, и число помещается в соответствующую позицию.
3.2 Демонстрация изображения
3.3 Отображение кода
public static void insertSort(int[] arr) {
if(arr==null)
return;
int len=arr.length;
//i控制循环次数，因为已经默认第一个数的位置是正确的，所以i的起始值为1，i<len，循环len-1次
for(int i=1;i<len;i++) {
int j=i;//变量j用来记录即将要排序的数的位置即目标数的原位置
int target=arr[j];//target用来记录即将要排序的那个数的值即目标值
//while循环用来为目标值在已经排好序的数中找到合适的位置，
//因为是从后向前比较，并且是与j-1位置的数比较，所以j>0
while(j>0 && target<arr[j-1]) {
//当目标数的值比它当前位置的前一个数的值小时，将前一个数的位置向后移一位。
//并且j--使得目标数继续与下一个元素比较
arr[j]=arr[j-1];
j--;
}
//更目标数的位置。
arr[j]=target;
//打印每次循环结束之后数组的排序状态（方便理解）
System.out.println("第"+(i)+"次循环之后效果："+Arrays.toString(arr));
}
}
4. Сортировка по холму
4.1 Основная идея
Сортировка по холму также называется «сокращенной инкрементной сортировкой».Принцип заключается в том, чтобы сначала разделить сортируемый массив на несколько подпоследовательностей, чтобы количество элементов в каждой подпоследовательности было небольшим, а затем выполнить сортировку вставками для каждой пары подпоследовательностей. После того, как массив в основном отсортирован, можно выполнить прямую сортировку вставками, чтобы завершить сортировку всего массива. Поэтому следует принять стратегию сегментации прыжков. Здесь вводится понятие «приращение», две группы записей, разделенные определенным приращением, объединяются в подпоследовательность, а затем непосредственно вставляется и сортируется каждая подпоследовательность, так что полученный результат будет в принципе упорядочен (т. самые маленькие спереди, большие сзади, большие посередине). Сортировка по Хиллу — это усовершенствованная версия сортировки с прямым вставкой.
4.2 Представление изображения
4.3 Отображение кода
public static void shellSort(int[] arr) {
if(arr==null)
return;
int len=arr.length;//数组的长度
int k=len/2;//初始的增量为数组长度的一半
//while循环控制按增量的值来划不同分子序列，每完成一次增量就减少为原来的一半
//增量的最小值为1，即最后一次对整个数组做直接插入排序
while(k>0) {
//里边其实就是升级版的直接插入排序了，是对每一个子序列进行直接插入排序，
//所以直接将直接插入排序中的‘1’变为‘k’就可以了。
for(int i=k;i<len;i++) {
int j=i;
int target=arr[i];
while(j>=k && target<arr[j-k]) {
arr[j]=arr[j-k];
j-=k;
}
arr[j]=target;
}
//不同增量排序后的结果
System.out.println("增量为"+k+"排序之后："+Arrays.toString(arr));
k/=2;
}
}
5. Сортировка слиянием
5.1 Основная идея
Общее обобщение состоит в том, чтобы рекурсивно разделить сверху вниз, а затем постепенно объединить снизу вверх.
рекурсивный раскол: Сначала разделите сортируемый массив на левую и правую подпоследовательности, а затем разделите левую и правую подпоследовательности на четыре подпоследовательности и так далее, пока минимальное количество элементов подпоследовательности не станет равным двум или одному.
постепенное слияние(Следует отметить, что слияние снизу вверх можно понимать как рекурсивный иерархический возврат): сортировать самую нижнюю левую подпоследовательность, затем сортировать вторую подпоследовательность слева направо, а затем сортировать две подпоследовательности.Отсортированные подпоследовательности объединяются и сортируется, а затем нижняя третья подпоследовательность сортируется слева направо..... После завершения слияния память завершает операцию сортировки массива
5.2 Демонстрация изображения
5.3 Отображение кода
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr= {3,8,6,2,1,8};
mergeSort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
/**
* 递归拆分
* @param arr 待拆分数组
* @param left 待拆分数组最小下标
* @param right 待拆分数组最大下标
*/
public static void mergeSort(int[] arr,int left,int right) {
int mid=(left+right)/2; //中间下标
if(left<right) {
mergeSort(arr,left,mid);//递归拆分左边
mergeSort(arr,mid+1,right);//递归拆分右边
sort(arr,left,mid,right);//合并左右
}
}
/**
* 合并两个有序子序列
* @param arr 待合并数组
* @param left 待合并数组最小下标
* @param mid 待合并数组中间下标
* @param right 待合并数组最大下标
*/
public static void sort(int[] arr,int left,int mid,int right) {
int[] temp=new int[right-left+1]; //临时数组，用来保存每次合并年之后的结果
int i=left;
int j=mid+1;
int k=0;//临时数组的初始下标
//这个while循环能够初步筛选出待合并的了两个子序列中的较小数
while(i<=mid && j<=right) {
if(arr[i]<=arr[j]) {
temp[k++]=arr[i++];
}else {
temp[k++]=arr[j++];
}
}
//将左边序列中剩余的数放入临时数组
while(i<=mid) {
temp[k++]=arr[i++];
}
//将右边序列中剩余的数放入临时数组
while(j<=right) {
temp[k++]=arr[j++];
}
//将临时数组中的元素位置对应到真真实的数组中
for(int m=0;m<temp.length;m++) {
arr[m+left]=temp[m];
}
}
6. Быстрая сортировка
6.1 Основная идея
Быстрая сортировка также использует стратегию «разделяй и властвуй», где вводится понятие «базового числа».
- Найти ссылочный номер (обычно в качестве ссылочного номера используется первый номер сортируемого массива)
- Разделите массив, поместив все элементы меньше или равные базовому числу слева, а все элементы больше базового числа справа.
- Повторяйте шаги 1 и 2, чтобы разделить левый и правый подразделы, пока каждый раздел не будет иметь только один номер.
6.2 Представление изображения
6.3 Отображение кода
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr= {72,6,57,88,60,42,83,73,48,85};
quickSort(arr,0,9);
System.out.println(Arrays.toString(arr));
}
/**
* 分区过程
* @param arr 待分区数组
* @param left 待分区数组最小下标
* @param right 待分区数组最大下标
*/
public static void quickSort(int[] arr,int left,int right) {
if(left<right) {
int temp=qSort(arr,left,right);
quickSort(arr,left,temp-1);
quickSort(arr,temp+1,right);
}
}
/**
* 排序过程
* @param arr 待排序数组
* @param left 待排序数组最小下标
* @param right 待排序数组最大下标
* @return 排好序之后基准数的位置下标，方便下次的分区
*/
public static int qSort(int[] arr,int left,int right) {
int temp=arr[left];//定义基准数，默认为数组的第一个元素
while(left<right) {//循环执行的条件
//因为默认的基准数是在最左边，所以首先从右边开始比较进入while循环的判断条件
//如果当前arr[right]比基准数大，则直接将右指针左移一位，当然还要保证left<right
while(left<right && arr[right]>temp) {
right--;
}
//跳出循环说明当前的arr[right]比基准数要小，那么直接将当前数移动到基准数所在的位置，并且左指针向右移一位（left++）
//这时当前数（arr[right]）所在的位置空出，需要从左边找一个比基准数大的数来填充。
if(left<right) {
arr[left++]=arr[right];
}
//下面的步骤是为了在左边找到比基准数大的数填充到right的位置。
//因为现在需要填充的位置在右边，所以左边的指针移动，如果arr[left]小于或者等于基准数，则直接将左指针右移一位
while(left<right && arr[left]<=temp) {
left++;
}
//跳出上一个循环说明当前的arr[left]的值大于基准数，需要将该值填充到右边空出的位置，然后当前位置空出。
if(left<right) {
arr[right--]=arr[left];
}
}
//当循环结束说明左指针和右指针已经相遇。并且相遇的位置是一个空出的位置，
//这时候将基准数填入该位置，并返回该位置的下标，为分区做准备。
arr[left]=temp;
return left;
}
7. Сортировка кучей
7.1 Основная идея
Перед этим поговорим о концепции кучи.кучаЭто специальное полное бинарное дерево, разделенное на кучу с большой вершиной и кучу с маленькой вершиной.
большая куча: значение каждого узла больше, чем значение его левого и правого дочерних узлов, и для сортировки по возрастанию используется большая верхняя куча.
небольшой верхний ворс: значение каждого узла меньше значения его левого и правого дочерних узлов, а небольшая верхняя куча используется для сортировки по убыванию.
Следовательно, необходимо построить массив для сортировки в формате большой верхней кучи, в это время верхний узел кучи имеет наибольшее число, и он обменивается с элементом последнего узла кучи. . Затем перестройте оставшиеся деревья в кучу, снова поменяйте местами первый узел и хвостовой узел и повторяйте, пока не останется только последний узел для завершения сортировки.
7.2 Демонстрация изображения
7.3 Отображение кода
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr= {72,6,57,88,60,42,83,73,48,85};
heapSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void heapSort(int[] arr) {
if(arr==null) {
return;
}
int len=arr.length;
//初始化大顶堆（从最后一个非叶节点开始，从左到右，由下到上）
for(int i=len/2-1;i>=0;i--) {
adjustHeap(arr,i,len);
}
//将顶节点和最后一个节点互换位置，再将剩下的堆进行调整
for(int j=len-1;j>0;j--) {
swap(arr,0,j);
adjustHeap(arr,0,j);
}
}
/**
* 整理树让其变成堆
* @param arr 待整理的数组
* @param i 开始的结点
* @param j 数组的长度
*/
public static void adjustHeap(int[] arr,int i,int j) {
int temp=arr[i];//定义一个变量保存开始的结点
//k就是该结点的左子结点下标
for(int k=2*i+1;k<j;k=2*k+1) {
//比较左右两个子结点的大小，k始终记录两者中较大值的下标
if(k+1<j && arr[k]<arr[k+1]) {
k++;
}
//经子结点中的较大值和当前的结点比较，比较结果的较大值放在当前结点位置
if(arr[k]>temp) {
arr[i]=arr[k];
i=k;
}else{//说明已经是大顶堆
break;
}
}
arr[i]=temp;
}
/**
* 交换数据
* @param arr
* @param num1
* @param num2
*/
public static void swap(int[] arr, int num1,int num2) {
int temp=arr[num1];
arr[num1]=arr[num2];
arr[num2]=temp;
}
8. Сортировка подсчетом
8.1 Основная идея
Сортировка подсчетом использует совершенно новую идею: вместо сортировки сравнением максимальное значение в сортируемом массиве + 1 используется в качестве длины временного массива, а затем временный массив используется для записи появления каждого элемента в массиве. массив для сортировки число раз. Наконец, временный массив просматривается.Поскольку он находится в порядке возрастания, он просматривается спереди назад, и индексы чисел со значением> 0 во временном массиве циклически вынимаются и помещаются в массив для сортировки в свою очередь, чтобы завершить сортировку. Эффективность сортировки подсчетом очень высока, но при этом жертвуется память, и есть ограничение, то есть значение сортируемого массива должно быть ограничено определенным диапазоном.
8.2 Представление изображения
8.3 Отображение кода
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr= {72,6,57,88,60,42,83,73,48,85};
countSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void countSort(int[] arr) {
if(arr==null)
return;
int len=arr.length;
//保存待排序数组中的最大值，目的是确定临时数组的长度（必须）
int maxNum=arr[0];
//保存待排序数组中的最小值，目的是确定最终遍历临时数组时下标的初始值（非必需，只是这样可以加快速度，减少循环次数）
int minNum=arr[0];
//for循环就是为了找到待排序数组的最大值和最小值
for(int i=1;i<len;i++) {
maxNum=maxNum>arr[i]?maxNum:arr[i];
minNum=minNum<arr[i]?minNum:arr[i];
}
//创建一个临时数组
int[] temp=new int[maxNum+1];
//for循环是为了记录待排序数组中每个元素出现的次数，并将该次数保存到临时数组中
for(int i=0;i<len;i++) {
temp[arr[i]]++;
}
//k=0用来记录待排序数组的下标
int k=0;
//遍历临时数组，重新为待排序数组赋值。
for(int i=minNum;i<temp.length;i++) {
while(temp[i]>0) {
arr[k++]=i;
temp[i]--;
}
}
}
9. Сортировка ведром
9.1 Основная идея
Сортировка ковша на самом деле является повышенной версией сортировки подсчета. Необходимо использовать функцию сопоставления для первого определения ограниченного количества ведер, а затем поместите элементы в массиве, чтобы сортироваться в разные ведра в соответствии с отношениями сопоставления функций. Данные был отличен. Например, числа в ведре A - все больше, чем в ведре B, или все меньше, чем числа в ведре B. Тем не менее, числа в ведрах A и B все еще не в порядке. Следовательно, нам нужно использовать другие методы сортировки (быстрые, вставка, объединение) для сортировки данных в каждом ведре с рядом элементов более одного. Наконец, поставьте элементы в ведро в массив, чтобы быть отсортированы в порядке.
9.2 Демонстрация изображения
9.3 Отображение кода
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr= {72,6,57,88,60,42,83,73,48,85};
bucketSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void bucketSort(int[] arr) {
if(arr==null)
return;
int len=arr.length;
//定义桶的个数，这里k的值要视情况而定，这里我们假设待排序数组里的数都是[0,100)之间的。
int k=10;
//用嵌套集合来模拟桶，外层集合表示桶，内层集合表示桶里边装的元素。
List<List<Integer>> bucket=new ArrayList<>();
//for循环初始化外层集合即初始化桶
for(int i=0;i<k;i++){
bucket.add(new ArrayList<>());
}
//循环是为了将待排序数组中的元素通过映射函数分别放入不同的桶里边
for(int i=0;i<len;i++) {
bucket.get(mapping(arr[i])).add(arr[i]);
}
//这个循环是为了将所有的元素个数大于1的桶里边的数据进行排序。
for(int i=0;i<k;i++) {
if(bucket.size()>1) {
//因为这里是用集合来模拟的桶所以用java写好的对集合排序的方法。
//其实应该自己写一个方法来排序的。
Collections.sort(bucket.get(i));
}
}
//将排好序的数重新放入待排序数组中
int m=0;
for(List<Integer> list:bucket) {
if(list.size()>0) {
for(Integer a:list) {
arr[m++]=a;
}
}
}
}
/**
* 映射函数
* @param num
* @return
*/
public static int mapping(int num) {
return num/10;
}
10. Сортировка по основанию
10.1 Основная идея
состоит в том, чтобы разделить данные для сортировки на несколькоключевые словаСортировка, то есть суть поразрядной сортировки — многоключевая сортировка. Идея сортировки по нескольким ключевым словам состоит в том, чтобы разделить данные для сортировки на несколько ключей сортировки: первый ключ сортировки, второй ключ сортировки, третий ключ сортировки... Затем отсортируйте данные для сортировки. согласно подразделам.
10.2 Демонстрация изображения
10.3 Отображение кода
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr= {720,6,57,88,60,42,83,73,48,85};
redixSort(arr,10,3);
System.out.println(Arrays.toString(arr));
}
public static void redixSort(int[] arr, int radix, int d) {
// 缓存数组
int[] tmp = new int[arr.length];
// buckets用于记录待排序元素的信息
// buckets数组定义了max-min个桶
int[] buckets = new int[radix];
for (int i = 0, rate = 1; i < d; i++) {
// 重置count数组，开始统计下一个关键字
Arrays.fill(buckets, 0);
// 将data中的元素完全复制到tmp数组中
System.arraycopy(arr, 0, tmp, 0, arr.length);
// 计算每个待排序数据的子关键字
for (int j = 0; j < arr.length; j++) {
int subKey = (tmp[j] / rate) % radix;
buckets[subKey]++;
}
for (int j = 1; j < radix; j++) {
buckets[j] = buckets[j] + buckets[j - 1];
}
// 按子关键字对指定的数据进行排序
for (int m = arr.length - 1; m >= 0; m--) {
int subKey = (tmp[m] / rate) % radix;
arr[--buckets[subKey]] = tmp[m];
}
rate *= radix;
}
}