一、排序算法
（一）冒泡排序
1. Python代码的实现
def bubbleSort(arr,n):
'''
:param arr: 需要排序的序列
:param n: 降序(True)或者升序(False)
:return: 排序后的序列
'''
for i in range(len(arr) - 1):
for j in range(len(arr) - 1 - i):
if arr[j] <= arr[j + 1] and n == True:
arr[j],arr[j + 1] = arr[j + 1],arr[j]
if arr[j] > arr[j + 1] and n == False:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
2. JavaScript代码的实现
function bubbleSort(arr,n)
{
for(let i = 0;i < arr.length - 1;i++)
{
for(let j = 0;j < arr.length - 1 - i;j++)
{
if(arr[j] <= arr[j + 1] && n == true)
{
let temp = arr[j];
arr[j + 1] = arr[j];
arr[j] = temp;
}
if(arr[j] > arr[j + 1] && n == false)
{
let temp = arr[j];
arr[j + 1] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}
（二）选择排序
1. Python代码的实现
def selectionSort(arr,n):
'''
:param arr: 需要排序的序列
:param n: 降序(True)或者升序(False)
:return: 排序后的序列
'''
for i in range(len(arr) - 1):
minIndex = i
for j in range(i + 1,len(arr)):
if arr[j] <= arr[minIndex] and n == True:
minIndex = j
if arr[j] > arr[minIndex] and n == False:
minIndex = j
if i != minIndex:
arr[i],arr[minIndex] = arr[minIndex],arr[i]
return arr
2. JavaScript代码的实现
function selectionSort(arr,n)
{
for(let i = 0;i < arr.length - 1;i++)
{
let minIndex = i;
for(let j = i + 1;j < arr.length;j++)
{
if(arr[j] <= arr[minIndex] && n==true)
{
minIndex = j;
}
if(arr[j] > arr[minIndex] && n==false)
{
minIndex = j;
}
}
let temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
return arr；
}
（三） 插入排序
1.Python代码的实现
def insertionSort(arr,n):
'''
:param arr: 需要排序的序列
:param n: 降序(True)或者升序(False)
:return: 排序后的序列
'''
for i in range(len(arr)):
preIndex = i - 1
current = arr[i]
while preIndex >= 0 and arr[preIndex] <= current and n == True:
arr[preIndex + 1] = arr[preIndex]
preIndex -= 1
while preIndex >= 0 and arr[preIndex] > current and n == False:
arr[preIndex + 1] = arr[preIndex]
preIndex -= 1
arr[preIndex + 1] = current
return arr
2. JavaScript代码的实现
function insertionSort(arr)
{
let preIndex,current;
for(let i = 1;i < arr.length;i++)
{
preIndex = i - 1;
current = arr[i];
while(preIndex >= 0 && arr[preIndex] <= current && n == true)
{
arr[preIndex + 1] = arr[preIndex];
preIndex--;
}
while(preIndex >= 0 && arr[preIndex] <= current && n == false)
{
arr[preIndex + 1] = arr[preIndex];
preIndex--;
}
arr[preIndex + 1] = current;
}
return arr;
}
（四）希尔排序（进阶版的插入排序）
1. Python代码实现
def shellSort(arr,space,n):
'''
:param arr: 需要排序的序列
:param space: 序列间隔
:param n: 降序(True)或者升序(False)
:return: 排序后的序列
'''
gap = 1
while gap < len(arr) / space:
gap = gap * space + 1
while gap > 0:
for i in range(gap,len(arr)):
j = i - gap
temp = arr[i]
while j >= 0 and arr[j] <= temp and n == True:
arr[j + gap] = arr[j]
j -= gap
while j >= 0 and arr[j] > temp and n == False:
arr[j + gap] = arr[j]
j -= gap
arr[j + gap] = temp
gap = math.floor(gap / space)
return arr
2. JavaScript代码的实现
function shellSort(arr,space,n)
{
let gap = 1;
while(gap < arr.length / space)
{
gap = gap * space + 1;
}
while(gap > 0)
{
for(let i = gap;i < arr.length;i++)
{
let temp = arr[i];
for(let j = i - gap;j >=0 && arr[j] <= temp && n == true ;j -= gap)
{
arr[j + gap ] = arr[j];
}
for(let j = i - gap;j >=0 && arr[j] > temp && n == false ;j -= gap)
{
arr[j + gap ] = arr[j];
}
arr[j + gap] = temp;
}
}
return arr;
}
（五）归并排序（分治法思想）
1. Python代码的实现
'''
归并排序实现的两种方法:
1. 自上而下的递归
2. 自下而上的迭代
此处，采用自上而下的递归方法，并将序列或子序列一分为二。
'''
import math
def mergeSort(arr):
if len(arr) < 2:
return arr
middle = math.floor(len(arr) / 2)
left,right = arr[0:middle],arr[middle:]
return merge(mergeSort(left),mergeSort(right))
def merge(left,right):
result = []
while left and right:
if left[0] < right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0))
while left:
result.append(left.pop(0))
while right:
result.append(right.pop(0))
return result
2.JavaScript代码的实现
function mergeSort(arr)
{
if(arr.length < 2)
{
return arr;
}
let middle = Math.floor(len(arr) / 2),left = arr.slice(0,middle),right = arr.slice(middle);
return merge(mergeSort(left),mergeSort(right));
}
function merge(left,right)
{
let result = [];
while(left.length && right.length)
{
if(left[0] <= right[0])
{
result.push(left.shift());
}
else
{
result.push(right.shift());
}
}
while(left.length)
{
result.push(left.shift());
}
while(right.length)
{
result.push(right.shift());
}
return result;
}
（六）快速排序
1. Python代码的实现
def quickSort(arr,left=None,right=None):
left = 0 if not isinstance(left,(int,float)) else left
right = len(arr) - 1 if not isinstance(right,(int,float)) else right
if left < right:
partitionIndex = partition(arr,left,right)
quickSort(arr,left,partitionIndex - 1)
quickSort(arr,partitionIndex + 1,right)
return arr
def partition(arr,left,right):
pivot = left
index = pivot + 1
i = index
while i <= right:
if arr[i] < arr[pivot]:
arr[i],arr[index] = arr[index],arr[i]
index += 1
i += 1
arr[pivot],arr[index - 1] = arr[index - 1],arr[pivot]
return index - 1
2. JavaScript代码的实现
function quickSort(arr,left,right)
{
let partitionIndex,
left = typeof left != 'number' ? 0 : left,
right = typeof right != 'number' ？ arr.length - 1: right;
if(left < right)
{
partitionIndex = partition(arr,left,right);
quickSort(arr,left,partitonIndex - 1);
quickSort(arr,partitionIndex + 1,right);
}
return arr;
}
function partition(arr,left,right)
{
let pivot = left,index = pivot + 1;
for(let i = index;i <= right; i++)
{
if(arr[i] < arr[pivot])
{
let temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
index++;
}
}
let temp = arr[pivot];
arr[pivot] = arr[index - 1];
arr[index - 1] = temp;
return index - 1
}
（七）堆排序
1. Python代码的实现
'''
堆排序的两种方法：
1. 大顶堆：每个节点的值大于或者等于其子节点的值，用于升序算法
2. 小顶堆：每个节点的值小于或者等于其子节点的值，用于降序算法
此处，采用大顶堆的方法进行排序。
'''
import math
def buildMaxHeap(arr):
for i in range(math.floor(len(arr) / 2),-1,-1):
heapify(arr,i)
def heapify(arr,i):
left = 2 * i + 1
right = 2 * i + 2
largest = i
if left < arrLen and arr[left] > arr[largest]:
largest = left
if right < arrLen and arr[right] > arr[largest]:
largest = right
if largest != i:
arr[i],arr[largest] = arr[largest],arr[i]
heapify(arr,largest)
def heapSort(arr):
global arrLen
arrLen = len(arr)
buildMaxHeap(arr)
for i in range(len(arr) - 1,0,-1):
arr[0],arr[i] = arr[i],arr[0]
arrLen -= 1
heapify(arr,0)
return arr
2.JavaScript代码的实现
let len;
function buildMaxHeap(arr)
{
len = arr.length;
for(let i = Math.floor(len / 2);i >= 0;i--)
{
heapify(arr,i);
}
}
function heapify(arr,i)
{
let left = 2 * i + 1,
right = 2 * i + 2,
largest = i;
if(left < len && arr[left] > arr[largest]
{
largest = left;
}
if(right < len && arr[right] > arr[largest]
{
largest = right;
}
if(largest != i)
{
let temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr,largest);
}
}
function heapSort(arr)
{
buildMaxHeap(arr);
for(let i =arr.length - 1; i > 0 ; i--)
{
let temp = arr[0];
arr[0] = arr[i];
arr[i] = twmp;
len--;
heapify(arr,0);
}
return arr;
}
（八）计数排序
1. Python代码的实现
def countingSort(arr):
bucketLen = max(arr) + 1
bucket = [0] * bucketLen
sortedIndex = 0
arrLen = len(arr)
for i in range(arrLen):
if not bucket[arr[i]]:
bucket[arr[i]] = 0
bucket[arr[i]] += 1
for j in range(bucketLen):
while bucket[j] > 0:
arr[sortedIndex] = j
sortedIndex += 1
bucket[j] -= 1
return arr
2. JavaScript代码的实现
function countingSort(arr)
{
let bucket = new Array(max(arr) + 1),
sortedIndex = 0,
arrLen = arr.length,
bucketLen = max(arr) + 1;
for(let i = 0; i < arrLen;i++)
{
if(!bucket[arr[i]])
{
bucket[arr[i]] = 0;
}
bucket[arr[i]]++;
}
for(let j = 0; j < bucketLen;j++)
{
while(bucket[j] > 0)
{
arr[sortedIndex++] = j;
bucket[j]--;
}
}
return arr;
}
（九）基数排序
1. Python代码的实现
def radix(arr):
digit = 0
max_digit = 1
max_value = max(arr)
while 10 ** max_digit < max_value:
max_digit += 1
while digit < max_digit:
temp = [[] for i in range(10)]
for i in arr:
t = int((i / 10 ** digit) % 10)
temp[t].append(i)
coll = []
for bucket in temp:
for i in bucket:
coll.append(i)
arr = coll
digit += 1
return arr
|