一、基本的排序算法
1、冒泡排序
基本思想：
n个数一共要进行n-1趟排序，每一趟排序都是两两比较，小的数一路交换着往前走，大的数就自然往后靠，每一趟排序都会确定一个数的最终位置。
#冒泡排序python实现
def BubbleSort():
arr = [9,5,12,8,3,11]
for i in range(len(arr)-1):
for j in range(i+1,len(arr)):
if arr[j]<arr[i]:
arr[i],arr[j] = arr[j],arr[i]
return arr
//冒泡排序c++实现
#include <iostream>
#include "stdio.h"
using namespace std;
void BubbleSort(){
int arr[6] = {9,5,12,8,3,11};
int length = sizeof(arr)/sizeof(arr[0]);
for(int i=0;i<length-1;i++){
for(int j=i+1;j<length;j++){
if(arr[j]<arr[i]){
int temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
}
}
}
2、选择排序
基本思想：
从下标0开始遍历整个数组，找到最小的数与下标为0的数交换位置，然后从下标1开始遍历数组，找到最小的与下标为1的数交换位置......直到遍历完整个数组。
#选择排序python实现
def SelectSort():
arr = [9,5,12,8,3,11]
for i in range(len(arr)):
indexOfmin = i
for j in range(i+1,len(arr)):
if arr[j]<arr[i]:
indexOfmin = j
if indexOfmin!=i:
arr[i],arr[indexOfmin] = arr[indexOfmin],arr[i]
return arr
//选择排序c++实现
#include <iostream>
#include "stdio.h"
using namespace std;
void SelectSort(){
int arr[6] = {9,5,12,8,3,11};
int length = sizeof(arr)/sizeof(arr[0]);
for(int i=0;i<length;i++){
int indexOfmin_number = i;
for(int j=i+1;j<length;j++){
if(arr[j]<arr[i]){
indexOfmin_number=j;
}
}
if(indexOfmin_number!=i){
int temp = arr[indexOfmin_number];
arr[indexOfmin_number] = arr[i];
arr[i] = temp;
}
}
}
3、插入排序
基本思想：
对于一个待排序的数组，把下标为0的第一个数字看作是“排好序”的数组，然后从下标为1的第二个数开始，依次与“排好序”的数字比较，并适当移动“排好序”的数字并把该数字插到合适的位置，直到整个数组遍历完毕。
#插入排序python实现
def InsertSort():
arr = [9,5,12,8,3,11]
for i in range(len(arr)-1):
for j in range(i+1,0,-1):
if arr[j]<arr[j-1]:
arr[j],arr[j-1] = arr[j-1],arr[j]
else:
break
return arr
//插入排序c++实现
#include <iostream>
#include "stdio.h"
using namespace std;
void InsertSort(){
int arr[6] = {9,5,12,8,3,11};
int length = sizeof(arr)/sizeof(arr[0]);
for(int i=0;i<length-1;i++){
for(int j=i+1;j>0;j--){
if(arr[j]<arr[j-1]){
int temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
}
}
}
4、快速排序
基本思想：
使用分治法（Divide and conquer）策略来把一个序列分为较小和较大的2个子序列，然后递归地排序两个子序列。
1、挑选基准值：从数列中挑出一个元素，称为“基准”（pivot），
2、分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成，
3、递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。
看这个图我觉得能很好的帮助你理解原理。
#快速排序python实现
def Partition(arr, left, right):#切分：找基准点
i,j = left,right
# i < j 意味着还没有找到基准点
while (i < j):
# 从右边开始，保证i < j并且arr[i]小于或者等于arr[j]，即左边的数小于等于右边的数
while (i < j and arr[i] <= arr[j]):
j-=1
# 跳出循环，两种可能：j >= i 或者arr[i]大于arr[j]。如果是前者，就直接跳出大循环了，返回基准点；如果是后者，那就意味着右边的数小于左边的数了，所以需要将两个数交换位置。
if (i < j):
arr[i],arr[j] = arr[j],arr[i]
#右边的数小于左边的数，交换位置之后就要从左边往右边开始遍历、比较、交换。
while (i < j and arr[i] <= arr[j]):
i+=1
if (i < j):
arr[i],arr[j] = arr[j],arr[i]
# i>=j 说明基准点已经找到了
return i
def QuickSort(arr,left,right):#递归调用：对由基准点分开的小数组进行排序
if (left<right):
pivot = Partition(arr,left,right)
#沿着基准点切开数组，然后对左右两边进行递归
QuickSort(arr,left,pivot-1)
QuickSort(arr,pivot+1,right)
return arr
print(QuickSort([9,5,12,8,3,11],0,5))
//快速排序c++实现
#include <iostream>
#include "stdio.h"
using namespace std;
int Partition(int arr[],int left,int right){
while(left<right){
while(left<right && arr[left]<arr[right]){
right -= 1;
}
if(arr[left]>=arr[right]){
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
while(left<right && arr[left]<arr[right]){
left += 1;
}
if(arr[left]>=arr[right]){
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
}
return left;
}
int QuickSort(int arr[],int left,int right){
if(left<right){
int pivot = Partition(arr,left,right);
QuickSort(arr,left,pivot-1);
QuickSort(arr,pivot+1,right);
}
return 0;
}
5、希尔排序
基本思想：
希尔排序又称为“缩小增量排序”。对于有n个待排序元素的序列，首先取一个整数step(step<n)作为间隔，将全部元素分为step个子序列(也就是把所有相隔距离为step的元素放在同一个子序列中)，然后在每个子序列中分别采用直接插入排序算法进行排序。所有子序列排序完毕之后得到新的待排序序列，然后缩小间隔step(比如说：ste/=2),重复上述过程直到step等于1。
#希尔排序python实现
def ShellSort(arr):
step = len(arr)//2
while step>=1:
for i in range(step,len(arr)):
for j in range(i,step-1,-step):
if arr[j]<arr[j-step]:
arr[j],arr[j-step] = arr[j-step],arr[j]
else:
break
step //= 2
return arr
//希尔排序c++实现
#include <iostream>
#include "stdio.h"
using namespace std;
void ShellSort(int arr[],int length){
int step = 1;
while(step < length/3){
step = step*3 + 1;
}
while(step>=1){
for (int i = 0; i < step; i++) {
int j = i+step;
while(j<length){
if(arr[j]<arr[j-step]){
int temp = arr[j];//先保存下标为j的值
int k = j-step;
while(k>=0&&temp<arr[k]){ //从j-step开始比较，把大于arr[j]的数往后挪，前面腾出位置存放arr[j]
arr[k+step] = arr[k];
k -= step;
}
arr[k+step] = temp;//arr[j]存放到最终合适的位置
}
j += step;
}
}
step /= 3;
}
}
6、堆排序
基本思想：
堆排序是利用堆这个数据结构而设计的一种排序算法。堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
- 将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆，此堆为初始的无序区；
- 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),且满足R[1,2...n-1]<=R[n];
- 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
主要步骤为：1、建堆；2、交换调整。
#堆排序python实现
def BuildHeap(arr,start,length):
while 2*start+1 <= length :
j = 2*start+1
if j<length and arr[j+1]>arr[j]:
j+=1
if arr[j] < arr[start]:
break
arr[start],arr[j] = arr[j],arr[start] #把大的数移到上面去
start = j
def HeapSort(arr):
length = len(arr)
for i in range(length//2,-1,-1): #构建一个堆
BuildHeap(arr,i,length-1)
length -= 1
while(length>0): #排序
arr[0],arr[length] = arr[length],arr[0]
length -= 1
BuildHeap(arr,0,length)
return arr
//堆排序c++实现
#include <iostream>
#include <vector>
using namespace std;
//辅助交换函数
void Swap(int &a, int &b){
int temp = a;
a = b;
b = temp;
}
//堆排序的核心是建堆,传入参数为数组，根节点位置，数组长度
void Heap_build(int a[], int root, int length){
int lchild = root * 2 + 1;//根节点的左子结点下标
if (lchild < length){ //左子结点下标不能超出数组的长度
int flag = lchild;//flag保存左右节点中最大值的下标
int rchild = lchild + 1;//根节点的右子结点下标
if (rchild < length){ //右子结点下标不能超出数组的长度(如果有的话)
if (a[rchild] > a[flag]){ //找出左右子结点中的最大值
flag = rchild;
}
}
if (a[root] < a[flag]){
//交换父结点和比父结点大的最大子节点
Swap(a[root], a[flag]);
//从此次最大子节点的那个位置开始递归建堆
Heap_build(a, flag, length);
}
}
}
void Heap_sort(int a[], int len){
for (int i = len / 2-1; i >= 0; --i) { //从最后一个非叶子节点的父结点开始建堆
Heap_build(a, i, len);
}
for (int j = len - 1; j > 0; --j){ //j表示数组此时的长度，因为len长度已经建过了，从len-1开始
Swap(a[0], a[j]);//交换首尾元素,将最大值交换到数组的最后位置保存
Heap_build(a, 0, j);//去除最后位置的元素重新建堆，此处j表示数组的长度，最后一个位置下标变为len-2
}
}
7、归并排序
基本思想：
归并排序的核心思想是“分治”。主要就是两个步骤：
分割：递归地把当前序列平均分割成两半。
#归并排序python实现
def merge_sort(alist):
if len(alist) <= 1:
return alist
# 将大数组分解成一个个只有一个元素的数组
num = len(alist) // 2
left = merge_sort(alist[:num])
right = merge_sort(alist[num:])
# 返回合并后的结果
return merge(left, right)
def merge(left, right):
'''合并操作，将两个有序数组left[]和right[]合并成一个大的有序数组'''
# l与r为两个有序数组left[]和right[]的下标索引
l, r = 0, 0
result = []
#两个有序数组left[]和right[]都没有合并完就一直比较下去
while l < len(left) and r < len(right):
if left[l] < right[r]:
result.append(left[l])
l += 1
else:
result.append(right[r])
r += 1
#跳出while循环，把两个有序数组left[]和right[]剩下的元素直接加到大数组后面
result += left[l:]
result += right[r:]
return result
print(merge_sort([9,5,12,8,3,11]))
//归并排序c++实现
#include<iostream>
#include<stdio.h>
using namespace std;
void mergearray(int a[],int first,int mid,int last,int result[]){
int i=first,j=mid+1;
int n=mid,m=last;
int k=0;
while(i<=n&&j<=m){
if(a[i]<=a[j])
result[k++]=a[i++];
else
result[k++]=a[j++];
}
while(i<=n){
result[k++]=a[i++];
}
while(j<=m){
result[k++]=a[j++];
}
for(i=0;i<k;i++){
a[first+i]=result[i];
}
}
void mergesort(int a[],int first,int last,int result[]){
if(first<last){
int mid=(first+last)/2;
mergesort(a,first,mid,result);
mergesort(a,mid+1,last,result);
mergearray(a,first,mid,last,result);
}
}
int MergeSort(int a[],int len){
int *temp=new int [len];
if(temp==NULL)
return 0;
else
mergesort(a,0,len-1,temp);
return 1;
}
int main(){
int arr[] = {9,5,12,8,3,11};
int n = sizeof(arr)/sizeof(arr[0]);
MergeSort(arr,n);
for(int i=0;i<n;i++)
{
printf("%d ",arr[i]);
}
}
网友评论