排序算法是用于按特定顺序（通常是数字顺序或字典顺序）排列列表或数组元素的方法。它们是计算机科学中有效组织数据的基础。这是理解如何将问题分解为步骤然后实现这些步骤的练习，即如何创建算法。这也是一种认识到解决问题的方法有多种，并且有些方法优于其他方法的练习。
我为什么要学习它？
- 这是一个递归思考（参见：合并排序和快速排序）和分而治之的简单实用示例。
- 这是一个简单但不平凡的算法分析示例（即大 o）。
- 这是一个传统的计算机科学入门主题，预计将被教授。
- 这是一个简单的示例，可以激发您为什么可能关心拥有比最简单的本机算法（即冒泡排序）更好的算法。
以下是一些常见的排序算法
冒泡排序
描述：如果相邻元素的顺序错误，则重复交换它们。
时间复杂度： o(n²)
用例：简单但对于大型数据集效率低下。
冒泡排序 github 要点
<p>var arr = [10, 55, 20, 4, 28, 69, 22, 85, 7, 37];</p>
<p>function bubblesort(arr)<br>
{<br>
var temp, i, j;</p>
<div class="highlight js-code-highlight">
<pre class="highlight plaintext">for(i = 0; i<arr.length; i++)
{
for(j = 0; j< arr.length; j++)
{
if (arr[j] > arr[j+1])
{
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
return arr;
}
立即学习“Java免费学习笔记（深入）”；
console.log(bubblesort(arr));
选择排序
描述：从未排序的部分中选择最小的元素，并将其与第一个未排序的元素交换。
时间复杂度： o(n²)
用例： 对于大型数据集效率较低，但易于实现。
选择排序 github 要点
<p>var arr = [10, 55, 20, 4, 28, 69, 22, 85, 7, 37];</p>
<p>function selectionsort(arr)<br>
{<br>
var min;<br>
for(var i = 0; i < arr.length; i++)<br>
{<br>
min = i;<br>
for(var j = i+1; j < arr.length; j++ )<br>
{<br>
if (arr[j] < arr[min])<br>
{<br>
min = j;<br>
}<br>
}</p>
<div class="highlight js-code-highlight">
<pre class="highlight plaintext"> if (min !== i) {
var s = arr[min];
arr[min] = arr[i];
arr[i] = s;
}
}
立即学习“Java免费学习笔记（深入）”；
返回arr;
}
console.log(selectionsort(arr));
插入排序
描述：通过将每个元素插入到正确的位置来构建排序列表，一次一个元素。
时间复杂度： o(n²)
用例：适用于小型数据集或接近排序的数组。
插入排序 github gist
<p>var arr = [10, 55, 20, 4, 28, 69, 22, 85, 7, 37];</p>
<p>function insertionsort(arr)<br>
{<br>
for(let i = 1; i< arr.length; i++)<br>
{<br>
let key= arr[i];<br>
let j = i - 1</p>
<div class="highlight js-code-highlight">
<pre class="highlight plaintext"> while (j >= 0 && key < arr[j]) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = key;
}
return arr;
}
立即学习“Java免费学习笔记（深入）”；
console.log(insertionsort(arr));
归并排序
描述：将数组分成两半，递归排序，然后合并排序后的两半。
时间复杂度： o(n log n)
用例：对于大型数据集有效，使用额外的空间进行合并。
合并排序 github gist
合并排序 2 github 要点
<p>var unsortedarr = [10, 55, 20, 4, 28, 69, 22, 85, 7, 37];</p>
<p>function merge(left, right)<br>
{<br>
const result = new array();</p>
<div class="highlight js-code-highlight">
<pre class="highlight plaintext">let i = j = 0;
while (i < left.length && j < right.length) {
if (left[i] < right[j]){
result.push(left[i]);
i++;
}else {
result.push(right[j]);
j++;
}
}
while (i < left.length) {
result.push(left[i]);
i++;
}
while (j < right.length) {
result.push(right[j]);
j++;
}
return result;
}
立即学习“Java免费学习笔记（深入）”；
函数 mergesort(arr)
{
if (arr.length
返回 arr;
const mid = math.floor(arr.length/2);
const la = new array();
const ra = new array();
for(let i = 0; i< mid; i++)
la.push(arr[i]);
for(let j = mid; j< arr.length; j++)
ra.push(arr[j]);
const leftsorted = mergesort(la);
const rightsorted = mergesort(ra);
return merge(leftsorted, rightsorted);
}
立即学习“Java免费学习笔记（深入）”；
console.log(mergesort(unsortedarr));
快速排序
描述： 选择一个主元，将数组划分为两个子数组：小于主元的元素和大于主元的元素，然后递归地对子数组进行排序。
时间复杂度： 平均为 o(n log n)，最坏情况为 o(n²)。
用例：快速且广泛用于大型数据集。
快速排序 github gist
<p>var arr = [10, 55, 20, 4, 28, 69, 22, 85, 7, 37];</p>
<p>function partition(arr, low, high)<br>
{<br>
const pivot = arr[high];</p>
<div class="highlight js-code-highlight">
<pre class="highlight plaintext">let i = low -1;
for(let j = low; j <= high -1; j++)
{
if (arr[j] < pivot) {
i++
swap(arr, i, j)
}
}
swap(arr, i+ 1, high);
return i + 1
}
立即学习“Java免费学习笔记（深入）”；
函数交换(arr, i, j)
{
让 temp = arr[i];
arr[i] = arr[j];
arr[j] = 温度;
}
函数快速排序(arr, low, high)
{
if (低
const po = 分区(arr, 低, 高);
quicksort(arr, low, po - 1);
quicksort(arr, po + 1, high);
}
return arr;
}
立即学习“Java免费学习笔记（深入）”；
console.log(quicksort(arr, 0, arr.length - 1));
堆排序
描述：将数组转换为堆数据结构，并反复提取最大元素构建排序数组。
时间复杂度： o(n log n)
用例：高效且不需要像合并排序那样额外的空间。
基数排序
描述：非比较排序算法，从最低有效数字开始到最高有效数字对元素进行逐位排序。
时间复杂度： o(nk)，其中 k 是位数。
用例：适用于使用固定长度键对数字或字符串进行排序。
桶排序
描述：将元素分成几个桶，然后对每个桶单独排序（通常使用另一种排序算法）。
时间复杂度： o(n + k)，其中 k 是桶的数量。
用例：当输入在一定范围内均匀分布时有效。
每种算法都有其优点和缺点，选择使用哪种算法取决于数据集的大小、内存限制以及数据是否部分排序。
让我们讨论一下我们应该多久练习一次。
