概述
java python算法
什么是排序算法？ (What is a Sorting Algorithm?)
Sorting algorithms are a set of instructions that take an array or list as an input and arrange the items into a particular order.
排序算法是一组指令，这些指令采用数组或列表作为输入并将项目按特定顺序排列。
Sorts are most commonly in numerical or a form of alphabetical (called lexicographical) order, and can be in ascending (A-Z, 0-9) or descending (Z-A, 9-0) order.
排序最常见的是数字形式或字母顺序(称为字典顺序)，并且可以升序(AZ，0-9)或降序(ZA，9-0)顺序。
为什么排序算法很重要 (Why Sorting Algorithms are Important)
Since sorting can often reduce the complexity of a problem, it is an important algorithm in Computer Science. These algorithms have direct applications in searching algorithms, database algorithms, divide and conquer methods, data structure algorithms, and many more.
由于排序通常可以降低问题的复杂性，因此它是计算机科学中的重要算法。 这些算法可直接应用于搜索算法，数据库算法，分治法，数据结构算法等等。
算法的权衡 (Trade-Offs of Algorithms)
When using different algorithms some questions have to be asked. How big is the collection being sorted? How much memory is at disposal to be used? Does the collection need to grow?
当使用不同的算法时，必须提出一些问题。 收集的物品有多大？ 有多少内存可供使用？ 收藏品需要增长吗？
The answers to these questions may determine what algorithm is going to work best for the situation. Some algorithms like merge sort may need a lot of space to run, while insertion sort is not always the fastest but it doesn't require many resources to run.
这些问题的答案可能会确定哪种算法最适合这种情况。 诸如归类排序之类的某些算法可能需要大量空间才能运行，而插入排序并不总是最快的，但它不需要太多资源即可运行。
You should determine what the requirements of the system are and its limitations before deciding what algorithm to use.
在决定使用哪种算法之前，应先确定系统的要求及其局限性。
一些常见的排序算法 (Some Common Sorting Algorithms)
Some of the most common sorting algorithms are:
一些最常见的排序算法是：
- Selection Sort 选择排序
- Bubble Sort 气泡排序
- Insertion Sort 插入排序
- Merge Sort 合并排序
- Quick Sort 快速排序
- Heap Sort 堆排序
- Counting Sort 计数排序
- Radix Sort 基数排序
- Bucket Sort 桶分类
But before we get into each of these, let's learn a bit more about what makes classifies a sorting algorithm.
但是，在深入探讨每种方法之前，让我们进一步了解使分类算法分类的原因。
排序算法的分类 (Classification of a Sorting Algorithm)
Sorting algorithms can be categorized based on the following parameters:
可以根据以下参数对排序算法进行分类：
Based on Number of Swaps or Inversion This is the number of times the algorithm swaps elements to sort the input.
Selection Sortrequires the minimum number of swaps.基于交换次数或反转次数这是算法交换元素以对输入进行排序的次数。
Selection Sort要求最少数量的交换。Based on Number of Comparisons This is the number of times the algorithm compares elements to sort the input. Using Big-O notation, the sorting algorithm examples listed above require at least
O(nlogn)comparisons in the best case andO(n^2)comparisons in the worst case for most of the outputs.基于比较次数这是算法比较元素以对输入进行排序的次数。 使用Big-O表示法 ，上面列出的排序算法示例在大多数情况下对于大多数输出至少需要
O(nlogn)比较，而在最坏情况下至少需要O(n^2)比较。Based on Recursion or Non-Recursion Some sorting algorithms, such as
Quick Sort, use recursive techniques to sort the input. Other sorting algorithms, such asSelection SortorInsertion Sort, use non-recursive techniques. Finally, some sorting algorithm, such asMerge Sort, make use of both recursive as well as non-recursive techniques to sort the input.基于递归或非递归一些排序算法(例如
Quick Sort)使用递归技术对输入进行排序。 其他排序算法(例如Selection Sort或Insertion Sort)使用非递归技术。 最后，一些排序算法(例如Merge Sort)利用递归和非递归技术对输入进行排序。Based on Stability Sorting algorithms are said to be
stableif the algorithm maintains the relative order of elements with equal keys. In other words, two equivalent elements remain in the same order in the sorted output as they were in the input.基于稳定性的排序算法被认为是
stable是该算法使用相同的键维持元素的相对顺序。 换句话说，两个等效元素在排序输出中的顺序与输入中的顺序相同。Insertion sort,Merge Sort, andBubble Sortare stableInsertion sort，Merge Sort和Bubble Sort稳定Heap SortandQuick Sortare not stableHeap Sort和Quick Sort不稳定Based on Extra Space Requirement Sorting algorithms are said to be
in placeif they require a constantO(1)extra space for sorting.基于额外空间要求，如果排序算法需要恒定的
O(1)额外空间来进行排序，则可以说已经in place。Insertion sortandQuick-sortarein placesort as we move the elements about the pivot and do not actually use a separate array which is NOT the case in merge sort where the size of the input must be allocated beforehand to store the output during the sort.Insertion sort和Quick-sort是in place我们围绕枢轴移动元素时in place排序，实际上并没有使用单独的数组，在合并排序中情况并非如此，在合并排序中，必须事先分配输入的大小以在输出期间存储输出分类。Merge Sortis an example ofout placesort as it require extra memory space for its operations.Merge Sort是一个例子out place的排序，因为它需要它的操作额外的内存空间。
任何基于比较的排序的最佳时间复杂度 (Best possible time complexity for any comparison based sorting)
Any comparison based sorting algorithm must make at least nLog2n comparisons to sort the input array, and Heapsort and merge sort are asymptotically optimal comparison sorts. This can be easily proved by drawing a decision tree diagram.
任何基于比较的排序算法都必须至少进行nLog2n个比较才能对输入数组进行排序，并且Heapsort和merge排序是渐近最优的比较排序。 通过绘制决策树图可以很容易地证明这一点。
桶分类 (Bucket Sort)
Bucket Sort is a comparison sort algorithm that operates on elements by dividing them into different buckets and then sorting these buckets individually. Each bucket is sorted individually using a separate sorting algorithm or by applying the bucket sort algorithm recursively.
存储桶排序是一种比较排序算法，可通过将元素划分为不同的存储桶然后分别对这些存储桶进行排序来对它们进行操作。 使用单独的排序算法或通过递归应用存储桶排序算法分别对每个存储桶进行排序。
Bucket Sort is mainly useful when the input is uniformly distributed over a range.
当输入在一个范围内均匀分布时，存储桶排序主要有用。
假设您面前有以下问题 (Assume you have the following problem in front of you)
You have been given a large array of floating point integers lying uniformly between the lower and upper bound. This array now needs to be sorted.
您获得了一大堆浮点整数，它们均匀地位于上下限之间。 现在需要对该数组进行排序。
A simple way to solve this problem would be to use another sorting algorithm such as Merge sort, Heap Sort or Quick Sort. However, these algorithms guarantee a best case time complexity of O(NlogN). However, using bucket sort, the above task can be completed in O(N)time.
解决此问题的一种简单方法是使用其他排序算法，例如合并排序，堆排序或快速排序。 但是，这些算法保证了O(NlogN)的最佳情况下时间复杂度。 但是，使用存储桶排序，可以在O(N)时间完成上述任务。
Let's have a closer look at it.
让我们仔细看看。
Consider that you need to create an array of lists, that is of buckets. Elements now need to be inserted into these buckets on the basis of their properties. Each of these buckets can then be sorted individually using Insertion Sort.
考虑到您需要创建一个列表数组，即存储桶。 现在，需要根据元素的属性将元素插入这些存储桶中。 然后，可以使用“插入排序”对每个存储桶分别进行排序。
桶分类的伪代码： (Pseudo Code for Bucket Sort:)
void bucketSort(float[] a,int n)
{
for(each floating integer 'x' in n)
{
insert x into bucket[n*x];
}
for(each bucket)
{
sort(bucket);
}
}计数排序 (Counting Sort)
Counting Sort is a sorting technique based on keys between a specific range. It works by counting the number of objects having distinct key values (kind of hashing). Then doing some arithmetic to calculate the position of each object in the output sequence.
计数排序是一种基于特定范围之间的键的排序技术。 它通过计算具有不同键值(哈希类型)的对象的数量来工作。 然后做一些算术计算每个对象在输出序列中的位置。
例： (Example:)
For simplicity, consider the data in the range 0 to 9.
Input data: 1, 4, 1, 2, 7, 5, 2
1) Take a count array to store the count of each unique object.
Index: 0 1 2 3 4 5 6 7 8 9
Count: 0 2 2 0 1 1 0 1 0 0
2) Modify the count array such that each element at each index
stores the sum of previous counts.
Index: 0 1 2 3 4 5 6 7 8 9
Count: 0 2 4 4 5 6 6 7 7 7
The modified count array indicates the position of each object in
the output sequence.
3) Output each object from the input sequence followed by
decreasing its count by 1.
Process the input data: 1, 4, 1, 2, 7, 5, 2. Position of 1 is 2.
Put data 1 at index 2 in output. Decrease count by 1 to place
next data 1 at an index 1 smaller than this index.物产 (Properties)
- Space complexity: O(K) 空间复杂度：O(K)
- Best case performance: O(n+K) 最佳性能：O(n + K)
- Average case performance: O(n+K) 平均案例表现：O(n + K)
- Worst case performance: O(n+K) 最坏情况下的性能：O(n + K)
- Stable: Yes (K is the number of distinct elements in the array) 稳定：是(K是数组中不同元素的数量)
用JavaScript实现 (Implementation in JavaScript)
let numbers = [1, 4, 1, 2, 7, 5, 2];
let count = [];
let i, z = 0;
let max = Math.max(...numbers);
// initialize counter
for (i = 0; i <= max; i++) {
count[i] = 0;
}
for (i=0; i < numbers.length; i++) {
count[numbers[i]]++;
}
for (i = 0; i <= max; i++) {
while (count[i]-- > 0) {
numbers[z++] = i;
}
}
// output sorted array
for (i=0; i < numbers.length; i++) {
console.log(numbers[i]);
}C ++实现 (C++ Implementation)
#include <iostream>
void countSort(int upperBound, int lowerBound, std::vector<int> numbersToSort) //lower and upper bounds of numbers in vector
{
int range = upperBound - lowerBound; //create a range large enough to get every number between the min and max
std::vector<int> counts (range); //initialize of counts of the size of the range
std::fill(counts.begin(), counts.end(), 0); //fill vector of zeros
for (int i = 0; i < numbersToSort.size(); i++)
{
int index = numbersToSort[i] - lowerBound; //For example, if 5 is the lower bound and numbersToSort[i] is 5. index will be 0 and the counts[index]+= 1; //count of 5 will be stored in counts[0]
}
std::cout << counts << std::endl;
}快速实施 (Swift Implementation)
func countingSort(_ array: [Int]) {
// Create an array to store the count of each element
let maxElement = array.max() ?? 0
var countArray = [Int](repeating: 0, count: Int(maxElement + 1))
for element in array {
countArray[element] += 1
}
var z = 0
var sortedArray = [Int](repeating: 0, count: array.count)
for index in 1 ..< countArray.count {
//print index element required number of times
while countArray[index] > 0 {
sortedArray[z] = index
z += 1
countArray[index] -= 1
}
}
print(sortedArray)
}插入排序 (Insertion Sort)
Insertion sort is a simple sorting algorithm for a small number of elements.
插入排序是一种针对少量元素的简单排序算法。
例： (Example:)
In Insertion sort, you compare the key element with the previous elements. If the previous elements are greater than the key element, then you move the previous element to the next position.
在插入排序中，您将key元素与之前的元素进行比较。 如果先前的元素大于key元素，则将先前的元素移动到下一个位置。
Start from index 1 to size of the input array.
从索引1开始到输入数组的大小。
[ 8 3 5 1 4 2 ]
[8 3 5 1 4 2]
Step 1 :
第1步 ：
key = 3 //starting from 1st index.
Here `key` will be compared with the previous elements.
In this case, `key` is compared with 8. since 8 > 3, move the element 8
to the next position and insert `key` to the previous position.
Result: [ 3 8 5 1 4 2 ]Step 2 :
第2步 ：
key = 5 //2nd index
8 > 5 //move 8 to 2nd index and insert 5 to the 1st index.
Result: [ 3 5 8 1 4 2 ]Step 3 :
第三步：
key = 1 //3rd index
8 > 1 => [ 3 5 1 8 4 2 ]
5 > 1 => [ 3 1 5 8 4 2 ]
3 > 1 => [ 1 3 5 8 4 2 ]
Result: [ 1 3 5 8 4 2 ]Step 4 :
第4步 ：
key = 4 //4th index
8 > 4 => [ 1 3 5 4 8 2 ]
5 > 4 => [ 1 3 4 5 8 2 ]
3 > 4 ≠> stop
Result: [ 1 3 4 5 8 2 ]Step 5 :
步骤5：
key = 2 //5th index
8 > 2 => [ 1 3 4 5 2 8 ]
5 > 2 => [ 1 3 4 2 5 8 ]
4 > 2 => [ 1 3 2 4 5 8 ]
3 > 2 => [ 1 2 3 4 5 8 ]
1 > 2 ≠> stop
Result: [1 2 3 4 5 8]The algorithm shown below is a slightly optimized version to avoid swapping the key element in every iteration. Here, the key element will be swapped at the end of the iteration (step).
下面显示的算法是经过稍微优化的版本，可避免在每次迭代中交换key元素。 此处， key元素将在迭代(步骤)结束时交换。
InsertionSort(arr[])
for j = 1 to arr.length
key = arr[j]
i = j - 1
while i > 0 and arr[i] > key
arr[i+1] = arr[i]
i = i - 1
arr[i+1] = keyHere is a detailed implementation in JavaScript:
这是JavaScript的详细实现：
function insertion_sort(A) {
var len = array_length(A);
var i = 1;
while (i < len) {
var x = A[i];
var j = i - 1;
while (j >= 0 && A[j] > x) {
A[j + 1] = A[j];
j = j - 1;
}
A[j+1] = x;
i = i + 1;
}
}A quick implementation in Swift is shown below:
Swift中的快速实现如下所示：
var array = [8, 3, 5, 1, 4, 2]
func insertionSort(array:inout Array<Int>) -> Array<Int>{
for j in 0..<array.count {
let key = array[j]
var i = j-1
while (i > 0 && array[i] > key){
array[i+1] = array[i]
i = i-1
}
array[i+1] = key
}
return array
}The Java example is shown below:
Java示例如下所示：
public int[] insertionSort(int[] arr)
for (j = 1; j < arr.length; j++) {
int key = arr[j]
int i = j - 1
while (i > 0 and arr[i] > key) {
arr[i+1] = arr[i]
i -= 1
}
arr[i+1] = key
}
return arr;And in c....
并在...
void insertionSort(int arr[], int n)
{
int i, key, j;
for (i = 1; i < n; i++)
{
key = arr[i];
j = i-1;
while (j >= 0 && arr[j] > key)
{
arr[j+1] = arr[j];
j = j-1;
}
arr[j+1] = key;
}
}特性： (Properties:)
- Space Complexity: O(1) 空间复杂度：O(1)
- Time Complexity: O(n), O(n* n), O(n* n) for Best, Average, Worst cases respectively. 时间复杂度：分别为最佳，平均和最差情况下的O(n)，O(n * n)，O(n * n)。
- Best Case: array is already sorted 最佳情况：数组已排序
- Average Case: array is randomly sorted 平均情况：数组随机排序
- Worst Case: array is reversely sorted. 最坏的情况：数组被反向排序。
- Sorting In Place: Yes 就地排序：是
- Stable: Yes 稳定：是的
堆排序 (Heapsort)
Heapsort is an efficient sorting algorithm based on the use of max/min heaps. A heap is a tree-based data structure that satisfies the heap property – that is for a max heap, the key of any node is less than or equal to the key of its parent (if it has a parent).
Heapsort是一种基于最大/最小堆的有效排序算法。 堆是满足堆属性的基于树的数据结构，也就是说，对于最大堆，任何节点的键小于或等于其父键(如果它具有父键)。
This property can be leveraged to access the maximum element in the heap in O(logn) time using the maxHeapify method. We perform this operation n times, each time moving the maximum element in the heap to the top of the heap and extracting it from the heap and into a sorted array. Thus, after n iterations we will have a sorted version of the input array.
使用maxHeapify方法，可以利用此属性在O(logn)时间内访问堆中的最大元素。 我们执行此操作n次，每次将堆中的最大元素移到堆的顶部，然后将其从堆中提取并排序到数组中。 因此，在n次迭代之后，我们将获得输入数组的排序版本。
The algorithm is not an in-place algorithm and would require a heap data structure to be constructed first. The algorithm is also unstable, which means when comparing objects with same key, the original ordering would not be preserved.
该算法不是就地算法，需要首先构建堆数据结构。 该算法也是不稳定的，这意味着当比较具有相同键的对象时，将不会保留原始顺序。
This algorithm runs in O(nlogn) time and O(1) additional space [O(n) including the space required to store the input data] since all operations are performed entirely in-place.
该算法在O(nlogn)时间和O(1)额外空间[O(n)包括存储输入数据所需的空间)中运行，因为所有操作都是完全就地执行的。
The best, worst and average case time complexity of Heapsort is O(nlogn). Although heapsort has a better worse-case complexity than quicksort, a well-implemented quicksort runs faster in practice. This is a comparison-based algorithm so it can be used for non-numerical data sets insofar as some relation (heap property) can be defined over the elements.
Heapsort的最佳，最差和平均情况下时间复杂度为O(nlogn)。 尽管堆排序比快速排序具有更好的最坏情况复杂性，但实践中快速实现的快速排序运行得更快。 这是一种基于比较的算法，因此，只要可以在元素上定义某种关系(堆属性)，它就可以用于非数值数据集。
An implementation in Java is as shown below :
Java实现如下所示：
import java.util.Arrays;
public class Heapsort {
public static void main(String[] args) {
//test array
Integer[] arr = {1, 4, 3, 2, 64, 3, 2, 4, 5, 5, 2, 12, 14, 5, 3, 0, -1};
String[] strarr = {"hope you find this helpful!", "wef", "rg", "q2rq2r", "avs", "erhijer0g", "ewofij", "gwe", "q", "random"};
arr = heapsort(arr);
strarr = heapsort(strarr);
System.out.println(Arrays.toString(arr));
System.out.println(Arrays.toString(strarr));
}
//O(nlogn) TIME, O(1) SPACE, NOT STABLE
public static <E extends Comparable<E>> E[] heapsort(E[] arr){
int heaplength = arr.length;
for(int i = arr.length/2; i>0;i--){
arr = maxheapify(arr, i, heaplength);
}
for(int i=arr.length-1;i>=0;i--){
E max = arr[0];
arr[0] = arr[i];
arr[i] = max;
heaplength--;
arr = maxheapify(arr, 1, heaplength);
}
return arr;
}
//Creates maxheap from array
public static <E extends Comparable<E>> E[] maxheapify(E[] arr, Integer node, Integer heaplength){
Integer left = node*2;
Integer right = node*2+1;
Integer largest = node;
if(left.compareTo(heaplength) <=0 && arr[left-1].compareTo(arr[node-1]) >= 0){
largest = left;
}
if(right.compareTo(heaplength) <= 0 && arr[right-1].compareTo(arr[largest-1]) >= 0){
largest = right;
}
if(largest != node){
E temp = arr[node-1];
arr[node-1] = arr[largest-1];
arr[largest-1] = temp;
maxheapify(arr, largest, heaplength);
}
return arr;
}
}Implementation in C++
用C ++实现
#include <iostream>
using namespace std;
void heapify(int arr[], int n, int i)
{
int largest = i;
int l = 2*i + 1;
int r = 2*i + 2;
if (l < n && arr[l] > arr[largest])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != i)
{
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n)
{
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i=n-1; i>=0; i--)
{
swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
void printArray(int arr[], int n)
{
for (int i=0; i<n; ++i)
cout << arr[i] << " ";
cout << "n";
}
int main()
{
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr)/sizeof(arr[0]);
heapSort(arr, n);
cout << "Sorted array is n";
printArray(arr, n);
}基数排序 (Radix Sort)
Prerequisite: Counting Sort
先决条件：计数排序
QuickSort, MergeSort, and HeapSort are comparison-based sorting algorithms. CountSort is not. It has the complexity of O(n+k), where k is the maximum element of the input array. So, if k is O(n), CountSort becomes linear sorting, which is better than comparison based sorting algorithms that have O(nlogn) time complexity.
QuickSort，MergeSort和HeapSort是基于比较的排序算法。 CountSort不是。 它的复杂度为O(n + k)，其中k是输入数组的最大元素。 因此，如果k为O(n)，则CountSort变为线性排序，这比具有O(nlogn)时间复杂度的基于比较的排序算法要好。
The idea is to extend the CountSort algorithm to get a better time complexity when k goes O(n2). Here comes the idea of Radix Sort.
想法是扩展CountSort算法，以在k变为O(n2)时获得更好的时间复杂度。 这里是基数排序的想法。
算法： (The Algorithm:)
For each digit i where i varies from the least significant digit to the most significant digit of a number, sort input array using countsort algorithm according to ith digit. We used count sort because it is a stable sort.
对于i从数字的最低有效位到最高有效位变化的每个数字i，请根据第i个数字使用countsort算法对输入数组进行排序。 我们使用计数排序是因为它是一种稳定的排序。
Example: Assume the input array is:
示例：假设输入数组为：
10, 21, 17, 34, 44, 11, 654, 123
10、21、17、34、44、11、654、123
Based on the algorithm, we will sort the input array according to the one's digit (least significant digit).
基于该算法，我们将根据一个数字(最低有效数字)对输入数组进行排序。
0: 101: 21 112:3: 1234: 34 44 6545:6:7: 178:9:
0：101：21 112：3：1234：34 44 6545：6：7：178：9：
So, the array becomes 10, 21, 11, 123, 24, 44, 654, 17.
因此，该数组变为10、21、11、123、24、44、654、17。
Now, we'll sort according to the ten's digit:
现在，我们将根据十位数字进行排序：
0:1: 10 11 172: 21 1233: 344: 445: 6546:7:8:9:
0：1：10 11 172：21 1233：344：445：6546：7：8：9：
Now, the array becomes : 10, 11, 17, 21, 123, 34, 44, 654.
现在，该数组变为：10、11、17、21、123、34、44、654。
Finally, we sort according to the hundred's digit (most significant digit):
最后，我们根据百位数(最高有效位数)进行排序：
0: 010 011 017 021 034 0441: 1232:3:4:5:6: 6547:8:9:
0：010 011 017 021 034 0441：1232：3：4：5：6：6547：8：9：
The array becomes : 10, 11, 17, 21, 34, 44, 123, 654 which is sorted. This is how our algorithm works.
数组变为：10、11、17、21、34、44、123、654，将其排序。 这就是我们的算法的工作方式。
An implementation in C:
用C实现：
void countsort(int arr[],int n,int place){
int i,freq[range]={0}; //range for integers is 10 as digits range from 0-9
int output[n];
for(i=0;i<n;i++)
freq[(arr[i]/place)%range]++;
for(i=1;i<range;i++)
freq[i]+=freq[i-1];
for(i=n-1;i>=0;i--){
output[freq[(arr[i]/place)%range]-1]=arr[i];
freq[(arr[i]/place)%range]--;
}
for(i=0;i<n;i++)
arr[i]=output[i];
}
void radixsort(ll arr[],int n,int maxx){ //maxx is the maximum element in the array
int mul=1;
while(maxx){
countsort(arr,n,mul);
mul*=10;
maxx/=10;
}
}选择排序 (Selection Sort)
Selection Sort is one of the simplest sorting algorithms. This algorithm gets its name from the way it iterates through the array: it selects the current smallest element, and swaps it into place.
选择排序是最简单的排序算法之一。 该算法的名称来自其遍历数组的方式：它选择当前最小的元素，并将其交换到位。
Here's how it works:
运作方式如下：
- Find the smallest element in the array and swap it with the first element. 在数组中找到最小的元素，并将其与第一个元素交换。
- Find the second smallest element and swap with with the second element in the array. 找到第二个最小的元素，并与数组中的第二个元素交换。
- Find the third smallest element and swap wit with the third element in the array. 找到第三个最小的元素，然后与数组中的第三个元素交换智慧。
- Repeat the process of finding the next smallest element and swapping it into the correct position until the entire array is sorted. 重复查找下一个最小元素并将其交换到正确位置的过程，直到对整个数组进行排序为止。
But, how would you write the code for finding the index of the second smallest value in an array?
但是，您将如何编写代码以查找数组中第二个最小值的索引？
An easy way is to notice that the smallest value has already been swapped into index 0, so the problem reduces to finding the smallest element in the array starting at index 1.
一种简单的方法是注意到最小值已经交换到索引0中，因此问题减少了，找到从索引1开始的数组中的最小元素。
Selection sort always takes the same number of key comparisons — N(N − 1)/2.
选择排序始终采用相同数量的键比较-N(N − 1)/ 2。
用C / C ++实现 (Implementation in C/C++)
The following C++ program contains an iterative as well as a recursive implementation of the Selection Sort algorithm. Both implementations are invoked in the main() function.
以下C ++程序包含“选择排序”算法的迭代和递归实现。 两种实现都在main()函数中调用。
#include <iostream>
#include <string>
using namespace std;
template<typename T, size_t n>
void print_array(T const(&arr)[n]) {
for (size_t i = 0; i < n; i++)
std::cout << arr[i] << ' ';
cout << "n";
}
int minIndex(int a[], int i, int j) {
if (i == j)
return i;
int k = minIndex(a, i + 1, j);
return (a[i] < a[k]) ? i : k;
}
void recurSelectionSort(int a[], int n, int index = 0) {
if (index == n)
return;
int k = minIndex(a, index, n - 1);
if (k != index)
swap(a[k], a[index]);
recurSelectionSort(a, n, index + 1);
}
void iterSelectionSort(int a[], int n) {
for (int i = 0; i < n; i++)
{
int min_index = i;
int min_element = a[i];
for (int j = i + 1; j < n; j++)
{
if (a[j] < min_element)
{
min_element = a[j];
min_index = j;
}
}
swap(a[i], a[min_index]);
}
}
int main() {
int recurArr[6] = { 100,35, 500, 9, 67, 20 };
int iterArr[5] = { 25, 0, 500, 56, 98 };
cout << "Recursive Selection Sort" << "n";
print_array(recurArr); // 100 35 500 9 67 20
recurSelectionSort(recurArr, 6);
print_array(recurArr); // 9 20 35 67 100 500
cout << "Iterative Selection Sort" << "n";
print_array(iterArr); // 25 0 500 56 98
iterSelectionSort(iterArr, 5);
print_array(iterArr); // 0 25 56 98 500
}用JavaScript实现 (Implementation in JavaScript)
function selection_sort(A) {
var len = A.length;
for (var i = 0; i < len - 1; i = i + 1) {
var j_min = i;
for (var j = i + 1; j < len; j = j + 1) {
if (A[j] < A[j_min]) {
j_min = j;
} else {}
}
if (j_min !== i) {
swap(A, i, j_min);
} else {}
}
}
function swap(A, x, y) {
var temp = A[x];
A[x] = A[y];
A[y] = temp;
}用Python实现 (Implementation in Python)
def seletion_sort(arr):
if not arr:
return arr
for i in range(len(arr)):
min_i = i
for j in range(i + 1, len(arr)):
if arr[j] < arr[min_i]:
min_i = j
arr[i], arr[min_i] = arr[min_i], arr[i]Java实现 (Implementation in Java)
public void selectionsort(int array[])
{
int n = array.length; //method to find length of array
for (int i = 0; i < n-1; i++)
{
int index = i;
int min = array[i]; // taking the min element as ith element of array
for (int j = i+1; j < n; j++)
{
if (array[j] < array[index])
{
index = j;
min = array[j];
}
}
int t = array[index]; //Interchange the places of the elements
array[index] = array[i];
array[i] = t;
}
}在MATLAB中的实现 (Implementation in MATLAB)
function [sorted] = selectionSort(unsorted)
len = length(unsorted);
for i = 1:1:len
minInd = i;
for j = i+1:1:len
if unsorted(j) < unsorted(minInd)
minInd = j;
end
end
unsorted([i minInd]) = unsorted([minInd i]);
end
sorted = unsorted;
end物产 (Properties)
Space Complexity: O(n)
空间复杂度： O(n)
Time Complexity: O(n2)
时间复杂度： O(n2)
Sorting in Place: Yes
就地排序： 是
Stable: No
稳定： 否
气泡排序 (Bubble Sort)
Just like the way bubbles rise from the bottom of a glass, bubble sort is a simple algorithm that sorts a list, allowing either lower or higher values to bubble up to the top. The algorithm traverses a list and compares adjacent values, swapping them if they are not in the correct order.
就像气泡从玻璃杯底部升起的方式一样， 气泡排序是一种简单的算法，可对列表进行排序，使较低或较高的值都可以气泡到顶部。 该算法遍历一个列表并比较相邻的值，如果它们的顺序不正确，则将其交换。
With a worst-case complexity of O(n^2), bubble sort is very slow compared to other sorting algorithms like quicksort. The upside is that it is one of the easiest sorting algorithms to understand and code from scratch.
与O(n ^ 2)的最坏情况复杂度相比，气泡排序与其他排序算法(如快速排序)相比非常慢。 好处是，它是从头开始理解和编码的最简单的排序算法之一。
From technical perspective, bubble sort is reasonable for sorting small-sized arrays or specially when executing sort algorithms on computers with remarkably limited memory resources.
从技术角度来看，冒泡排序对于对小型数组进行排序是合理的，特别是在内存资源非常有限的计算机上执行排序算法时。
例： (Example:)
首先通过列表： (First pass through the list:)
Starting with
[4, 2, 6, 3, 9], the algorithm compares the first two elements in the array, 4 and 2. It swaps them because 2 < 4:[2, 4, 6, 3, 9]从
[4, 2, 6, 3, 9]，该算法比较数组4和2中的前两个元素。由于2 <4：[2, 4, 6, 3, 9]2，4，6，3，9[4, 2, 6, 3, 9]，它交换了它们。It compares the next two values, 4 and 6. As 4 < 6, these are already in order, and the algorithm moves on:
[2, 4, 6, 3, 9]它比较下两个值4和6。当4 <6时，它们已经按顺序排列，并且算法继续进行：
[2, 4, 6, 3, 9]The next two values are also swapped because 3 < 6:
[2, 4, 3, 6, 9]接下来的两个值也被交换，因为3 <6：
[2, 4, 3, 6, 9]- The last two values, 6 and 9, are already in order, so the algorithm does not swap them. 最后两个值6和9已经按顺序排列，因此算法不会交换它们。
第二遍列表： (Second pass through the list:)
2 < 4, so there is no need to swap positions:
[2, 4, 3, 6, 9]2 <4，因此无需交换头寸：
[2, 4, 3, 6, 9]The algorithm swaps the next two values because 3 < 4:
[2, 3, 4, 6, 9]该算法交换下两个值，因为3 <4：
[2, 3, 4, 6, 9]No swap as 4 < 6:
[2, 3, 4, 6, 9]没有交换，因为4 <6：
[2, 3, 4, 6, 9]Again, 6 < 9, so no swap occurs:
[2, 3, 4, 6, 9]同样，6 <9，因此不会发生交换：
[2, 3, 4, 6, 9]
The list is already sorted, but the bubble sort algorithm doesn't realize this. Rather, it needs to complete an entire pass through the list without swapping any values to know the list is sorted.
该列表已经排序，但是冒泡排序算法无法实现。 相反，它需要完成整个列表传递，而无需交换任何值来知道列表已排序。
第三遍列表： (Third pass through the list:)
[2, 4, 3, 6, 9]=>[2, 4, 3, 6, 9][2, 4, 3, 6, 9]=>[2, 4, 3, 6, 9][2, 4, 3, 6, 9]=>[2, 4, 3, 6, 9][2, 4, 3, 6, 9]=>[2, 4, 3, 6, 9][2, 4, 3, 6, 9]=>[2, 4, 3, 6, 9][2, 4, 3, 6, 9]=>[2, 4, 3, 6, 9][2, 4, 3, 6, 9]=>[2, 4, 3, 6, 9][2, 4, 3, 6, 9]=>[2, 4, 3, 6, 9]
Clearly bubble sort is far from the most efficient sorting algorithm. Still, it's simple to wrap your head around and implement yourself.
显然，气泡排序远非最有效的排序算法。 尽管如此，还是可以轻松实现自己的目标。
物产 (Properties)
- Space complexity: O(1) 空间复杂度：O(1)
- Best case performance: O(n) 最佳案例表现：O(n)
- Average case performance: O(n*n) 平均案例表现：O(n * n)
- Worst case performance: O(n*n) 最差情况的性能：O(n * n)
- Stable: Yes 稳定：是的
影片说明 (Video Explanation)
Bubble sort algorithm
气泡排序算法
JavaScript中的示例 (Example in JavaScript)
let arr = [1, 4, 7, 45, 7,43, 44, 25, 6, 4, 6, 9],
sorted = false;
while(!sorted) {
sorted = true;
for(var i=0; i < arr.length; i++) {
if(arr[i] < arr[i-1]) {
let temp = arr[i];
arr[i] = arr[i-1];
arr[i-1] = temp;
sorted = false;
}
}
}Java中的示例。 (Example in Java.)
public class BubbleSort {
static void sort(int[] arr) {
int n = arr.length;
int temp = 0;
for(int i=0; i < n; i++){
for(int x=1; x < (n-i); x++){
if(arr[x-1] > arr[x]){
temp = arr[x-1];
arr[x-1] = arr[x];
arr[x] = temp;
}
}
}
}
public static void main(String[] args) {
for(int i=0; i < 15; i++){
int arr[i] = (int)(Math.random() * 100 + 1);
}
System.out.println("array before sortingn");
for(int i=0; i < arr.length; i++){
System.out.print(arr[i] + " ");
}
bubbleSort(arr);
System.out.println("n array after sortingn");
for(int i=0; i < arr.length; i++){
System.out.print(arr[i] + " ");
}
}
}C ++中的示例 (Example in C++)
// Recursive Implementation
void bubblesort(int arr[], int n)
{
if(n==1) //Initial Case
return;
bool swap_flag = false;
for(int i=0;i<n-1;i++) //After this pass the largest element will move to its desired location.
{
if(arr[i]>arr[i+1])
{
int temp=arr[i];
arr[i]=arr[i+1];
arr[i+1]=temp;
swap_flag = true;
}
}
// IF no two elements were swapped in the loop, then return, as array is sorted
if(swap_flag == false)
return;
bubblesort(arr,n-1); //Recursion for remaining array
}Swift中的示例 (Example in Swift)
func bubbleSort(_ inputArray: [Int]) -> [Int] {
guard inputArray.count > 1 else { return inputArray } // make sure our input array has more than 1 element
var numbers = inputArray // function arguments are constant by default in Swift, so we make a copy
for i in 0..<(numbers.count - 1) {
for j in 0..<(numbers.count - i - 1) {
if numbers[j] > numbers[j + 1] {
numbers.swapAt(j, j + 1)
}
}
}
return numbers // return the sorted array
}Python范例 (Example in Python)
def bubbleSort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1] :
arr[j], arr[j+1] = arr[j+1], arr[j]
print(arr)PHP中的示例 (Example in PHP)
function bubble_sort($arr) {
$size = count($arr)-1;
for ($i=0; $i<$size; $i++) {
for ($j=0; $j<$size-$i; $j++) {
$k = $j+1;
if ($arr[$k] < $arr[$j]) {
// Swap elements at indices: $j, $k
list($arr[$j], $arr[$k]) = array($arr[$k], $arr[$j]);
}
}
}
return $arr;// return the sorted array
}
$arr = array(1,3,2,8,5,7,4,0);
print("Before sorting");
print_r($arr);
$arr = bubble_sort($arr);
print("After sorting by using bubble sort");
print_r($arr);C中的例子 (Example in C)
#include <stdio.h>
int BubbleSort(int array[], int n);
int main(void) {
int arr[] = {10, 2, 3, 1, 4, 5, 8, 9, 7, 6};
BubbleSort(arr, 10);
for (int i = 0; i < 10; i++) {
printf("%d", arr[i]);
}
return 0;
}
int BubbleSort(int array[], n)
{
for (int i = 0 ; i < n - 1; i++)
{
for (int j = 0 ; j < n - i - 1; j++) //n is length of array
{
if (array[j] > array[j+1]) // For decreasing order use
{
int swap = array[j];
array[j] = array[j+1];
array[j+1] = swap;
}
}
}
}快速排序 (Quick Sort)
Quick sort is an efficient divide and conquer sorting algorithm. Average case time complexity of Quick Sort is O(nlog(n)) with worst case time complexity being O(n^2) depending on the selection of the pivot element, which divides the current array into two sub arrays.
快速排序是一种有效的分而治之排序算法。 快速排序的平均情况下时间复杂度为O(nlog(n))，最坏情况下的时间复杂度为O(n ^ 2)，具体取决于枢纽元素的选择，该枢纽元素将当前数组分为两个子数组。
For instance, the time complexity of Quick Sort is approximately O(nlog(n)) when the selection of pivot divides original array into two nearly equal sized sub arrays.
例如，当选择枢轴将原始数组分成两个几乎相等大小的子数组时，快速排序的时间复杂度大约为O(nlog(n)) 。
On the other hand, if the algorithm, which selects of pivot element of the input arrays, consistently outputs 2 sub arrays with a large difference in terms of array sizes, quick sort algorithm can achieve the worst case time complexity of O(n^2).
另一方面，如果选择输入数组的枢轴元素的算法持续输出2个子数组，数组的大小差异很大，则快速排序算法可以实现O(n ^ 2)的最坏情况下的时间复杂度。 )。
The steps involved in Quick Sort are:
快速排序涉及的步骤是：
- Choose an element to serve as a pivot, in this case, the last element of the array is the pivot. 选择一个元素作为枢轴，在这种情况下，数组的最后一个元素是枢轴。
- Partitioning: Sort the array in such a manner that all elements less than the pivot are to the left, and all elements greater than the pivot are to the right. 分区：按以下方式对数组进行排序：小于枢轴的所有元素都在左侧，大于枢轴的所有元素都在右侧。
- Call Quicksort recursively, taking into account the previous pivot to properly subdivide the left and right arrays. (A more detailed explanation can be found in the comments below) 递归调用Quicksort，并考虑到先前的枢轴以正确细分左数组和右数组。 (更详细的解释可以在下面的评论中找到)
各种语言的示例实现 (Example Implementations in Various Languages)
用JavaScript实现： (Implementation in JavaScript:)
const arr = [6, 2, 5, 3, 8, 7, 1, 4];
const quickSort = (arr, start, end) => {
if(start < end) {
// You can learn about how the pivot value is derived in the comments below
let pivot = partition(arr, start, end);
// Make sure to read the below comments to understand why pivot - 1 and pivot + 1 are used
// These are the recursive calls to quickSort
quickSort(arr, start, pivot - 1);
quickSort(arr, pivot + 1, end);
}
}
const partition = (arr, start, end) => {
let pivot = end;
// Set i to start - 1 so that it can access the first index in the event that the value at arr[0] is greater than arr[pivot]
// Succeeding comments will expound upon the above comment
let i = start - 1,
j = start;
// Increment j up to the index preceding the pivot
while (j < pivot) {
// If the value is greater than the pivot increment j
if (arr[j] > arr[pivot]) {
j++;
}
// When the value at arr[j] is less than the pivot:
// increment i (arr[i] will be a value greater than arr[pivot]) and swap the value at arr[i] and arr[j]
else {
i++;
swap(arr, j, i);
j++;
}
}
//The value at arr[i + 1] will be greater than the value of arr[pivot]
swap(arr, i + 1, pivot);
//You return i + 1, as the values to the left of it are less than arr[i+1], and values to the right are greater than arr[i + 1]
// As such, when the recursive quicksorts are called, the new sub arrays will not include this the previously used pivot value
return i + 1;
}
const swap = (arr, firstIndex, secondIndex) => {
let temp = arr[firstIndex];
arr[firstIndex] = arr[secondIndex];
arr[secondIndex] = temp;
}
quickSort(arr, 0, arr.length - 1);
console.log(arr);用C实现 (Implementation in C)
#include<stdio.h>
void swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}
int partition (int arr[], int low, int high)
{
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high- 1; j++)
{
if (arr[j] <= pivot)
{
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
void quickSort(int arr[], int low, int high)
{
if (low < high)
{
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", arr[i]);
printf("n");
}
int main()
{
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr)/sizeof(arr[0]);
quickSort(arr, 0, n-1);
printf("Sorted array: n");
printArray(arr, n);
return 0;
}在Python3中实现 (Implementation in Python3)
import random
z=[random.randint(0,100) for i in range(0,20)]
def quicksort(z):
if(len(z)>1):
piv=int(len(z)/2)
val=z[piv]
lft=[i for i in z if i<val]
mid=[i for i in z if i==val]
rgt=[i for i in z if i>val]
res=quicksort(lft)+mid+quicksort(rgt)
return res
else:
return z
ans1=quicksort(z)
print(ans1)在MATLAB中的实现 (Implementation in MATLAB)
a = [9,4,7,3,8,5,1,6,2];
sorted = quicksort(a,1,length(a));
function [unsorted] = quicksort(unsorted, low, high)
if low < high
[pInd, unsorted] = partition(unsorted, low, high);
unsorted = quicksort(unsorted, low, pInd-1);
unsorted = quicksort(unsorted, pInd+1, high);
end
end
function [pInd, unsorted] = partition(unsorted, low, high)
i = low-1;
for j = low:1:high-1
if unsorted(j) <= unsorted(high)
i = i+1;
unsorted([i,j]) = unsorted([j,i]);
end
end
unsorted([i+1,high]) = unsorted([high,i+1]);
pInd = i+1;
endThe space complexity of quick sort is O(n) . This is an improvement over other divide and conquer sorting algorithms, which take O(nlong(n)) space.
快速排序的空间复杂度为O(n) 。 这是对其他占用O(nlong(n))空间的分而治之排序算法的改进。
Quick sort achieves this by changing the order of elements within the given array. Compare this with the merge sort algorithm which creates 2 arrays, each length n/2, in each function call.
快速排序通过更改给定数组中元素的顺序来实现。 将此与合并排序算法进行比较，该算法在每个函数调用中创建2个数组，每个数组的长度为n/2 。
However there does exist the problem of this sorting algorithm being of time O(n*n) if the pivot is always kept at the middle. This can be overcomed by utilizing a random pivot
但是，如果枢轴始终保持在中间，则确实存在这种排序算法的时间为O(n*n)的问题。 这可以通过利用随机枢轴来克服
复杂 (Complexity)
Best, average, worst, memory: n log(n)n log(n)n 2log(n). It's not a stable algorithm, and quicksort is usually done in-place with O(log(n)) stack space.
最佳，平均，最差的内存： n log(n)n log(n)n 2log(n)。 这不是一个稳定的算法，快速排序通常是在O(log(n))堆栈空间中就地完成的。
The space complexity of quick sort is O(n). This is an improvement over other divide and conquer sorting algorithms, which take O(n log(n)) space.
快速排序的空间复杂度为O(n)。 这是对其他占用O(n log(n))空间的分而治之排序算法的改进。
Timsort (Timsort)
Timsort is a fast sorting algorithm working at stable O(N log(N)) complexity.
Timsort是一种以稳定的O(N log(N))复杂度工作的快速排序算法。
Timsort is a blend of Insertion Sort and Mergesort. This algorithm is implemented in Java’s Arrays.sort() as well as Python’s sorted() and sort(). The smaller parts are sorted using Insertion Sort and are later merged together using Mergesort.
Timsort是插入排序和合并排序的混合。 该算法在Java的Arrays.sort()以及Python的sorted()和sort()中实现。 较小的部分使用“插入排序”进行排序，然后使用Mergesort合并在一起。
A quick implementation in Python:
用Python快速实现：
def binary_search(the_array, item, start, end):
if start == end:
if the_array[start] > item:
return start
else:
return start + 1
if start > end:
return start
mid = round((start + end)/ 2)
if the_array[mid] < item:
return binary_search(the_array, item, mid + 1, end)
elif the_array[mid] > item:
return binary_search(the_array, item, start, mid - 1)
else:
return mid
"""
Insertion sort that timsort uses if the array size is small or if
the size of the "run" is small
"""
def insertion_sort(the_array):
l = len(the_array)
for index in range(1, l):
value = the_array[index]
pos = binary_search(the_array, value, 0, index - 1)
the_array = the_array[:pos] + [value] + the_array[pos:index] + the_array[index+1:]
return the_array
def merge(left, right):
"""Takes two sorted lists and returns a single sorted list by comparing the
elements one at a time.
[1, 2, 3, 4, 5, 6]
"""
if not left:
return right
if not right:
return left
if left[0] < right[0]:
return [left[0]] + merge(left[1:], right)
return [right[0]] + merge(left, right[1:])
def timsort(the_array):
runs, sorted_runs = [], []
length = len(the_array)
new_run = [the_array[0]]
# for every i in the range of 1 to length of array
for i in range(1, length):
# if i is at the end of the list
if i == length - 1:
new_run.append(the_array[i])
runs.append(new_run)
break
# if the i'th element of the array is less than the one before it
if the_array[i] < the_array[i-1]:
# if new_run is set to None (NULL)
if not new_run:
runs.append([the_array[i]])
new_run.append(the_array[i])
else:
runs.append(new_run)
new_run = []
# else if its equal to or more than
else:
new_run.append(the_array[i])
# for every item in runs, append it using insertion sort
for item in runs:
sorted_runs.append(insertion_sort(item))
# for every run in sorted_runs, merge them
sorted_array = []
for run in sorted_runs:
sorted_array = merge(sorted_array, run)
print(sorted_array)
timsort([2, 3, 1, 5, 6, 7])复杂： (Complexity:)
Tim sort has a stable Complexity of O(N log(N)) and compares really well with Quicksort. A comparison of complexities can be found on this chart.
Tim排序具有O(N log(N))的稳定复杂度，与Quicksort相比确实非常好。 在此图表上可以找到复杂程度的比较。
合并排序 (Merge Sort)
Merge Sort is a Divide and Conquer algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves. The major portion of the algorithm is given two sorted arrays, and we have to merge them into a single sorted array. The whole process of sorting an array of N integers can be summarized into three steps-
合并排序是一种分而治之算法。 它将输入数组分为两半，将自己称为两半，然后合并两个排序的两半。 该算法的主要部分提供了两个排序数组，我们必须将它们合并为一个排序数组。 对N个整数数组进行排序的整个过程可以概括为三个步骤：
- Divide the array into two halves. 将阵列分为两半。
- Sort the left half and the right half using the same recurring algorithm. 使用相同的循环算法对左半部分和右半部分进行排序。
- Merge the sorted halves. 合并分类的两半。
There is something known as the Two Finger Algorithm that helps us merge two sorted arrays together. Using this subroutine and calling the merge sort function on the array halves recursively will give us the final sorted array we are looking for.
有一种称为“ 两指算法”的东西，可以帮助我们将两个排序的数组合并在一起。 使用此子例程并递归地对两半数组调用合并排序函数，将为我们提供所需的最终排序数组。
Since this is a recursion based algorithm, we have a recurrence relation for it. A recurrence relation is simply a way of representing a problem in terms of its subproblems.
由于这是基于递归的算法，因此我们具有递归关系。 递归关系只是按照子问题表示问题的一种方式。
T(n) = 2 * T(n / 2) + O(n)
T(n) = 2 * T(n / 2) + O(n)
Putting it in plain English, we break down the subproblem into two parts at every step and we have some linear amount of work that we have to do for merging the two sorted halves together at each step.
用简单的英语来说，我们在每个步骤将子问题分解成两部分，并且在将每个步骤中的两个半部分合并在一起时，我们需要做一些线性工作。
复杂 (Complexity)
The biggest advantage of using Merge sort is that the time complexity is only n*log(n) to sort an entire Array. It is a lot better than n^2 running time of bubble sort or insertion sort.
使用合并排序的最大优点是，对整个数组进行排序的时间复杂度仅为n * log(n)。 它比冒泡排序或插入排序的n ^ 2运行时间好得多。
Before we write code, let us understand how merge sort works with the help of a diagram.
在编写代码之前，让我们了解在图表的帮助下合并排序是如何工作的。
- Initially we have an array of 6 unsorted integers Arr(5, 8, 3, 9, 1, 2) 最初，我们有6个未排序整数Arr(5，8，3，9，1，2)的数组
- We split the array into two halves Arr1 = (5, 8, 3) and Arr2 = (9, 1, 2). 我们将数组分为两部分Arr1 =(5，8，3)和Arr2 =(9，1，2)。
- Again, we divide them into two halves: Arr3 = (5, 8) and Arr4 = (3) and Arr5 = (9, 1) and Arr6 = (2) 同样，我们将它们分为两半：Arr3 =(5，8)和Arr4 =(3)和Arr5 =(9，1)和Arr6 =(2)
- Again, we divide them into two halves: Arr7 = (5), Arr8 = (8), Arr9 = (9), Arr10 = (1) and Arr6 = (2) 同样，我们将它们分为两半：Arr7 =(5)，Arr8 =(8)，Arr9 =(9)，Arr10 =(1)和Arr6 =(2)
- We will now compare the elements in these sub arrays in order to merge them. 现在，我们将比较这些子数组中的元素以合并它们。
特性： (Properties:)
- Space Complexity: O(n) 空间复杂度：O(n)
- Time Complexity: O(n*log(n)). The time complexity for the Merge Sort might not be obvious from the first glance. The log(n) factor that comes in is because of the recurrence relation we have mentioned before. 时间复杂度：O(n * log(n))。 乍一看，合并排序的时间复杂性可能并不明显。 出现log(n)因子是由于我们之前提到的递归关系。
- Sorting In Place: No in a typical implementation 就地排序：在典型实施中为否
- Stable: Yes 稳定：是的
- Parallelizable :yes (Several parallel variants are discussed in the third edition of Cormen, Leiserson, Rivest, and Stein's Introduction to Algorithms.) 可并行化：是的(在Cormen，Leiserson，Rivest和Stein的算法简介的第三版中讨论了多个并行变体。)
C ++实现 (C++ Implementation)
void merge(int array[], int left, int mid, int right)
{
int i, j, k;
// Size of left sublist
int size_left = mid - left + 1;
// Size of right sublist
int size_right = right - mid;
/* create temp arrays */
int Left[size_left], Right[size_right];
/* Copy data to temp arrays L[] and R[] */
for(i = 0; i < size_left; i++)
{
Left[i] = array[left+i];
}
for(j = 0; j < size_right; j++)
{
Right[j] = array[mid+1+j];
}
// Merge the temp arrays back into arr[left..right]
i = 0; // Initial index of left subarray
j = 0; // Initial index of right subarray
k = left; // Initial index of merged subarray
while (i < size_left && j < size_right)
{
if (Left[i] <= Right[j])
{
array[k] = Left[i];
i++;
}
else
{
array[k] = Right[j];
j++;
}
k++;
}
// Copy the remaining elements of Left[]
while (i < size_left)
{
array[k] = Left[i];
i++;
k++;
}
// Copy the rest elements of R[]
while (j < size_right)
{
array[k] = Right[j];
j++;
k++;
}
}
void mergeSort(int array[], int left, int right)
{
if(left < right)
{
int mid = (left+right)/2;
// Sort first and second halves
mergeSort(array, left, mid);
mergeSort(array, mid+1, right);
// Finally merge them
merge(array, left, mid, right);
}
}JavaScript实现 (JavaScript Implementation)
function mergeSort (arr) {
if (arr.length < 2) return arr;
var mid = Math.floor(arr.length /2);
var subLeft = mergeSort(arr.slice(0,mid));
var subRight = mergeSort(arr.slice(mid));
return merge(subLeft, subRight);
}First we check the length of the array. If it is 1 then we simply return the array. This would be our base case. Else, we will find out the middle value and divide the array into two halves. We will now sort both of the halves with recursive calls to MergeSort function.
首先，我们检查数组的长度。 如果它是1，那么我们只返回数组。 这将是我们的基本情况。 否则，我们将找出中间值并将数组分为两半。 现在，我们将对MergeSort函数的递归调用对这两个部分进行排序。
function merge (a,b) {
var result = [];
while (a.length >0 && b.length >0)
result.push(a[0] < b[0]? a.shift() : b.shift());
return result.concat(a.length? a : b);
}When we merge the two halfs, we store the result in an auxilliary array. We will compare the starting element of left array to the starting element of right array. Whichever is lesser will be pushed into the results array and we will remove it from there respective arrays using [shift() operator. If we still end up with values in either of left or right array, we would simply concatenate it in the end of the result. Here is the sorted result:
当我们将两半合并时，我们将结果存储在辅助数组中。 我们将比较左数组的起始元素和右数组的起始元素。 取较小者将推入结果数组，然后使用[shift()运算符将其从相应的数组中删除。 如果我们仍然以left或right数组中的值作为结尾，则只需将其连接到结果的末尾即可。 这是排序的结果：
var test = [5,6,7,3,1,3,15];
console.log(mergeSort(test));
>> [1, 3, 3, 5, 6, 7, 15]合并排序YouTube教程 (A Merge Sort YouTube Tutorial)
Here's a good YouTube video that walks through the topic in detail.
这是一个很好的YouTube视频， 详细介绍了该主题 。
JS中的实现 (Implementaion in JS)
const list = [23, 4, 42, 15, 16, 8, 3]
const mergeSort = (list) =>{
if(list.length <= 1) return list;
const middle = list.length / 2 ;
const left = list.slice(0, middle);
const right = list.slice(middle, list.length);
return merge(mergeSort(left), mergeSort(right));
}
const merge = (left, right) => {
var result = [];
while(left.length || right.length) {
if(left.length && right.length) {
if(left[0] < right[0]) {
result.push(left.shift())
} else {
result.push(right.shift())
}
} else if(left.length) {
result.push(left.shift())
} else {
result.push(right.shift())
}
}
return result;
}
console.log(mergeSort(list)) // [ 3, 4, 8, 15, 16, 23, 42 ]用C实现 (Implementation in C)
#include<stdlib.h>
#include<stdio.h>
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(int arr[], int l, int r)
{
if (l < r)
{
int m = l+(r-l)/2;
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
void printArray(int A[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", A[i]);
printf("n");
}
int main()
{
int arr[] = {12, 11, 13, 5, 6, 7};
int arr_size = sizeof(arr)/sizeof(arr[0]);
printf("Given array is n");
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);
printf("nSorted array is n");
printArray(arr, arr_size);
return 0;用C ++实现 (Implementation in C++)
Let us consider array A = {2,5,7,8,9,12,13} and array B = {3,5,6,9,15} and we want array C to be in ascending order as well.
让我们考虑数组A = {2,5,7,8,9,12,13}和数组B = {3,5,6,9,15}，我们也希望数组C升序。
void mergesort(int A[],int size_a,int B[],int size_b,int C[])
{
int token_a,token_b,token_c;
for(token_a=0, token_b=0, token_c=0; token_a<size_a && token_b<size_b; )
{
if(A[token_a]<=B[token_b])
C[token_c++]=A[token_a++];
else
C[token_c++]=B[token_b++];
}
if(token_a<size_a)
{
while(token_a<size_a)
C[token_c++]=A[token_a++];
}
else
{
while(token_b<size_b)
C[token_c++]=B[token_b++];
}
}用Python实现 (Implementation in Python)
def merge(left,right,compare):
result = []
i,j = 0,0
while (i < len(left) and j < len(right)):
if compare(left[i],right[j]):
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
while (i < len(left)):
result.append(left[i])
i += 1
while (j < len(right)):
result.append(right[j])
j += 1
return result
def merge_sort(arr, compare = lambda x, y: x < y):
#Used lambda function to sort array in both(increasing and decresing) order.
#By default it sorts array in increasing order
if len(arr) < 2:
return arr[:]
else:
middle = len(arr) // 2
left = merge_sort(arr[:middle], compare)
right = merge_sort(arr[middle:], compare)
return merge(left, right, compare)
arr = [2,1,4,5,3]
print(merge_sort(arr))Java实现 (Implementation in Java)
public class mergesort {
public static int[] mergesort(int[] arr,int lo,int hi) {
if(lo==hi) {
int[] ba=new int[1];
ba[0]=arr[lo];
return ba;
}
int mid=(lo+hi)/2;
int arr1[]=mergesort(arr,lo,mid);
int arr2[]=mergesort(arr,mid+1,hi);
return merge(arr1,arr2);
}
public static int[] merge(int[] arr1,int[] arr2) {
int i=0,j=0,k=0;
int n=arr1.length;
int m=arr2.length;
int[] arr3=new int[m+n];
while(i<n && j<m) {
if(arr1[i]<arr2[j]) {
arr3[k]=arr1[i];
i++;
}
else {
arr3[k]=arr2[j];
j++;
}
k++;
}
while(i<n) {
arr3[k]=arr1[i];
i++;
k++;
}
while(j<m) {
arr3[k]=arr2[j];
j++;
k++;
}
return arr3;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int arr[]= {2,9,8,3,6,4,10,7};
int[] so=mergesort(arr,0,arr.length-1);
for(int i=0;i<arr.length;i++)
System.out.print(so[i]+" ");
}
}Java范例 (Example in Java)
public class mergesort {
public static int[] mergesort(int[] arr, int lo, int hi) {
if (lo == hi) {
int[] ba = new int[1];
ba[0] = arr[lo];
return ba;
}
int mid = (lo + hi) / 2;
int arr1[] = mergesort(arr, lo, mid);
int arr2[] = mergesort(arr, mid + 1, hi);
return merge(arr1, arr2);
}
public static int[] merge(int[] arr1, int[] arr2) {
int i = 0, j = 0, k = 0;
int n = arr1.length;
int m = arr2.length;
int[] arr3 = new int[m + n];
while (i < n && j < m) {
if (arr1[i] < arr2[j]) {
arr3[k] = arr1[i];
i++;
} else {
arr3[k] = arr2[j];
j++;
}
k++;
}
while (i < n) {
arr3[k] = arr1[i];
i++;
k++;
}
while (j < m) {
arr3[k] = arr2[j];
j++;
k++;
}
return arr3;
}
public static void main(String[] args) {
int arr[] = {2, 9, 8, 3, 6, 4, 10, 7};
int[] so = mergesort(arr, 0, arr.length - 1);
for (int i = 0; i < arr.length; i++)
System.out.print(so[i] + " ");
}
}翻译自: https://www.freecodecamp.org/news/sorting-algorithms-explained-with-examples-in-python-java-and-c/
java python算法
最后
以上就是美丽期待为你收集整理的java python算法_用Python，Java和C ++示例解释的排序算法的全部内容，希望文章能够帮你解决java python算法_用Python，Java和C ++示例解释的排序算法所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复