【数据结构】-排序算法总结
文章目录
【数据结构】-排序算法总结1 冒泡排序（BubbleSort）1.1 算法思想1.2 例题1.3 核心代码
2 选择排序（SelectSort）2.1 算法思想2.2 例题2.3 核心代码
3 插入排序3.1 算法思想3.2 例题3.3 核心代码
4 快速排序4.1 算法思想4.2 例题4.3 核心代码
5 归并排序5.1 算法思想5.2 例题5.3 核心代码
6 堆排序6.1 算法思想6.2 例题6.3 核心代码
堆构建大顶堆完整代码
7 基数排序7.1 基本概念7.2 算法思想7.3 例题7.4 核心代码7.5 完整代码
参考
1 冒泡排序（BubbleSort）
1.1 算法思想
从左向右扫描数据，选择最大是数据，放在右边要点
比较相邻的两个数，如果右边的数大于左边的数就进行交换
1.2 例题
排序：10、1、35、61、89、36、55
初始状态： 10 1 35 61 89 36 55
1 10 35 61 89 36 55 (比较相邻的两个数，如果右边大于左边就进行交换)
1 10 35 61 36 89 55
1 10 35 61 36 55 {89} (经过6次比较，将89沉末排序序列末尾)
1 10 35 36 55 {61 89} (经过5次比较，将61沉末排序序列末尾)
...
{1 10 35 36 55 61 89}
1.3 核心代码
每次需要找到最大的数，放在右边【需要找n-1次】
{
每次比较的最大次数为【n-1次，并每次循环减1】
}
void BubbleSort(int list[], int n)
// @ int list[] 数组数据
// @ int n 数据的个数
{
for(int i=0;i<n-1;i++)
{
for(int j=0;j<n-i-1;j++) // 每次循环过程中比较的次数
{
if(list[j]>list[j+1])
std::swap(list[j],list[j+1]); //交换
}
}
}
2 选择排序（SelectSort）
2.1 算法思想
从当前未排序的整数中找一个最小的整数，将它放在已排序的整数列表的最后要点
选择排序选最小的，往左边选
2.2 例题
排序：49、38、65、97、76、13、27
初始状态： 49 38 65 97 76 13 27
{13} 38 65 97 76 49 27 (第1次，选择最小的13和49交换)
{13 27} 65 97 76 49 38 (第2次，选择最小的27和38交换)
{13 27 38} 97 76 49 65 (第3次，选择最小的38和65交换)
{13 27 38 49} 76 97 65 (第4次，选择最小的49和97交换)
{13 27 38 49 65} 97 76 (第5次，选择最小的65和76交换)
{13 27 38 49 65 76 97} (第6次，选择最小的76和97交换)
2.3 核心代码
每次需要找到最大的数，放在左边【需要找n-1次】
{
}
void SelectSort(int *list, const int n)
{
for(int i=0;i<n-1;i++)
{
int min = i; //定义最小的数
for(int j=i+1 ;j<n; j++) // 选择出小的从左边开始放
{
if(list[j]<list[min]) // 选择出小的
min=j;
}
std::swap(list[i],list[min]); //交换
}
}
3 插入排序
3.1 算法思想
将【一个记录插入】到已排好序的序列中，从而得到一个新的有序序列
（将序列的第一个数据看成是第一个有序的子序列）
使用哨兵，用于临时存储和判断数组边界
3.2 例题
排序4、9、7、20、3、16、18
初始状态： {4} 9 7 20 3 16 18
{4 9} 7 20 3 16 18 (第一趟排序)
{4 7 9} 20 3 16 18 (第二趟排序)
{4 7 9 20} 3 16 18 (第三趟排序)
{3 4 7 9 20} 16 18 (第四趟排序)
{3 4 7 9 16 20} 18 (第五趟排序)
{3 4 7 9 16 18 20} (第六趟排序)
3.3 核心代码
比如第三趟排序中
{4 7 9 20} 3 16 18
out
in
out指向3，将3提出来
a[in-1] > 3
将20向后移动
直到找到 3 插入的位置
template<class T>
void InsertionSort(T *a,int n)
// @ a 数组a可以是不同类型
{
int in,out;
// 开始时out=0已经出去
for(out=1;out<n;out++)
{
T temp = a[out];
in = out;
while(in>0&&a[in-1]>temp)
{
a[in] = a[in-1]; // 将数向后移动
in--;
}
a[in] = temp;
}
}
4 快速排序
4.1 算法思想
pivot：选取枢轴(left or right or 随机)比较交换，将数据以枢枢轴分为两部分(左边小于枢轴，右边大于枢轴)左右两边进行递归
4.2 例题
排序 6、1、2、7、9、3、4、5、10、8
i j
初始状态 6 1 2 7 9 3 4 5 10 8
pivot
从左向右找比 pivot 大， 从右向左找比 privot 小的
6 1 2 7 9 3 4 5 10 8
i j
交换后 6 1 2 5 9 3 4 7 10 8
i j
交换后 6 1 2 5 4 3 9 7 10 8
j i
i>j 3 1 2 5 4 6 9 7 10 8 【i>j，不进行交换，但将基准和 j 交换】
然后以 6(j) 为分界点进行 递归
4.3 核心代码
方法一
template<class T>
void QuickSort(T *a,const int left , const int right)
{
if(left < right)
{
// 选枢轴进行划分
int i = left;
int j = right+1; // [下面需要++和--]
int pivot = a[left]; // 左边的做枢轴
// 左边找到一个比枢轴大的，右边找到一个比枢轴小的
do{
do i++ ;while(a[i]<pivot);
do j-- ;while(a[j]>pivot);
if(i<j) swap(a[i],a[j]);
}while(i<j);
swap(a[j],a[left]); //把枢轴交换到中间去（只能和j交换，j找到的数小于枢纽）
QuickSort(a,left,j-1); //左边的一半进行递归
QuickSort(a,j+1,right); //右边的一半进行递归
}
}
方法二
void quick_sort(int q[], int l, int r)
{
if (l >= r) return;
int i = l - 1, j = r + 1; // 先移动
x = q[l + r >> 1]; // 随机选择枢轴 [或者选择左边]【？？？选择右边，有问题】
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
quick_sort(q, l, j), quick_sort(q, j + 1, r); // 递归处理左右两端
}
5 归并排序
5.1 算法思想
5.2 例题
排序：6、3、2、7、1、5、8、4
5.3 核心代码
新建了一个数组
void merge_sort(int q[], int l, int r)
{
if (l >= r) return;
int mid = l + r >> 1; // 选择分界点
merge_sort(q, l, mid);
merge_sort(q, mid + 1, r); // 排序左边和右边
int k = 0, i = l, j = mid + 1; // 归并
while (i <= mid && j <= r)
if (q[i] < q[j]) tmp[k ++ ] = q[i ++ ];
else tmp[k ++ ] = q[j ++ ];
while (i <= mid) tmp[k ++ ] = q[i ++ ]; // 左右两边可能没有循环完成
while (j <= r) tmp[k ++ ] = q[j ++ ];
for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j]; // 把值放回来
}
6 堆排序
6.1 算法思想
把未排序的数据一个一个放入堆里，然后在一个一个取出来
6.2 例题
将62、3、90、25、33、8、12、9、43、66从大到小排列
6.3 核心代码
利用写好的头文件
#include <iostream>
#include "MaxHeap.h"
using namespace std;
int main()
{
MaxHeap<int> h(100);
int arr[] = {62,3,90,25,33,8,12,9,43,66};
for(int i=0;i<10;i++) // 放入堆
h.Push(arr[i]);
for(int i=0;i<10;i++) // 取出来
{
arr[i]=h.Top();
h.Pop();
}
for(int i=0;i<10;i++)
cout<< arr[i]<<" ";
cout<<endl;
cout << "Hello world!" << endl;
return 0;
}
堆
堆数据结构是一种数组对象，可以把它看出一颗完全二叉树。树中的每一个结点与数组中存放该节点值的那个元素所对应。完全二叉树数组
操作
插入新节点——向上渗透
删除根节点——向下渗透
Parent = (i-1)/2
left = 2*1+1
right = 2*i+2 = left+1
构建大顶堆
核心代码
插入新的节点
1.先插入到最后
2.然后向上渗透
template <class T>
void MaxHeap<T>::Push(const T& e)
{
if(currentSize == maxSize) throw "MaxHeap is full.";
heapArray[currentSize] = e; // 插入的点放在最后
trickleUp(currentSize); // 向上渗透
currentSize++; // 堆里面的数据 +1
}
template <class T>
void MaxHeap<T>::trickleUp(int index)
{
int parent = (index-1)/2;
T bottom = heapArray[index]; // 保存最后的节点(即将要插入的节点)
while(index > 0 && heapArray[parent] < bottom)
{
heapArray[index] = heapArray[parent];
index = parent;
parent = (parent-1)/2;
}
heapArray[index] = bottom; // 插入新节点
}
删除根节点
先将最后一个数放在根节点，然后向下渗透
`current` 表示最后一 空位 `--current` 表示最后一个数
template <class T>
void MaxHeap<T>::Pop()
{
heapArray[0] = heapArray[--currentSize]; // 最后一个数放在根节点
trickleDown(0); // 下沉
}
template <class T>
void MaxHeap<T>::trickleDown(int index)
{
int largerChild;
T top = heapArray[index]; // 临时的根保存起来
while(index < currentSize/2) // 到最后一层的上一层
{
int leftChild = 2*index +1; // 左儿子
int rightChild = leftChild + 1; // 右儿子
if(rightChild < currentSize && heapArray[leftChild] < heapArray[rightChild]) // 有右儿子，而且左儿子小于右儿子
largerChild = rightChild;
else
largerChild = leftChild;
if(top >= heapArray[largerChild])
break;
heapArray[index] = heapArray[largerChild];
index = largerChild;
}
heapArray[index] = top;
}
完整代码
// MaxHeap.h
#ifndef _MAX_HEAP_
#define _MAX_HEAP_
template <class T>
class MaxHeap
{
public:
MaxHeap(int mx=10);
virtual ~MaxHeap();
bool IsEmpty();
void Push(const T&);
void Pop();
const T& Top() const;
private:
T* heapArray;
int maxSize;
int currentSize;
void trickleUp(int index);
void trickleDown(int index);
};
template <class T>
MaxHeap<T>::MaxHeap(int mx)
{
if(mx<1) throw "max size must be >=1.";
maxSize = mx;
currentSize = 0;
heapArray = new T[maxSize];
}
template <class T>
MaxHeap<T>::~MaxHeap()
{
delete[] heapArray;
}
template <class T>
bool MaxHeap<T>::IsEmpty() // 判断是否为空
{
return currentSize==0;
}
template <class T>
void MaxHeap<T>::Push(const T& e)
{
if(currentSize == maxSize) throw "MaxHeap is full.";
heapArray[currentSize] = e; // 插入的点放在最后
trickleUp(currentSize); // 向上渗透
currentSize++;
}
template <class T>
void MaxHeap<T>::trickleUp(int index)
{
int parent = (index-1)/2;
T bottom = heapArray[index]; // 保存最后的节点
while(index > 0 && heapArray[parent] < bottom)
{
heapArray[index] = heapArray[parent];
index = parent;
parent = (parent-1)/2;
}
heapArray[index] = bottom;
}
template <class T>
const T& MaxHeap<T>::Top() const // 查看根节点数
{
return heapArray[0];
}
template <class T>
void MaxHeap<T>::Pop()
{
heapArray[0] = heapArray[--currentSize];
trickleDown(0);
}
template <class T>
void MaxHeap<T>::trickleDown(int index)
{
int largerChild;
T top = heapArray[index]; // 临时的根保存起来
while(index < currentSize/2) // 到最后一层的上一层
{
int leftChild = 2*index +1; // 左儿子
int rightChild = leftChild + 1; // 右儿子
if(rightChild < currentSize && heapArray[leftChild] < heapArray[rightChild]) // 有右儿子，而且左儿子小于右儿子
largerChild = rightChild;
else
largerChild = leftChild;
if(top >= heapArray[largerChild])
break;
heapArray[index] = heapArray[largerChild];
index = largerChild;
}
heapArray[index] = top;
}
#endif // _MAX_HEAP_
主程序
#include <iostream>
#include "MaxHeap.h"
using namespace std;
int main()
{
MaxHeap<int> h(100);
cout<<h.IsEmpty()<<endl;
h.Push(20);
h.Push(30);
h.Push(15);
cout<<h.Top()<<endl;
h.Pop();
h.Pop();
cout<<h.Top()<<endl;
cout << "Hello world!" << endl;
return 0;
}
7 基数排序
注意基数排序有两种：一种是高位优先，一种是低位优先（本文只讲低位优先，即先排个位，再排十位）
7.1 基本概念
十进制的基数是10，二进制的基数是2
7.2 算法思想
遍历所有数据，找出元素的最大位 （d位）先将所有数据，按照最低位的值进行排序…然后次低位…
7.3 例题
排序数据：179、208、306、93、859、984、55、9、271、33
将数据按照个位排序的结果为
个位数（第一遍）179、208、306、93、859、984、55、9、271、33桶十位数（第二遍）271、93、33、984、55、306、208、179、859、9百位数（第三遍）306、208、9、33、55、271、179、984、859、93
f[0]306-208-99-33-55-93f[1]271179f[2]208-271f[3]93-3333306f[4]984f[5]5555f[6]306f[7]271-179859f[8]208984-859984
个位数（第一遍）排序后的结果为：
271、93、33、984、55、306、208、179、859、9
个位数（第二遍）排序后的结果为：
306、208、9、33、55、271、179、984、859、93
百位数 （第三次）排序后的结果为：
9、33、55、93、179、208、271、306、859、984
7.4 核心代码
统计最大数有几位
// @data[] 存储数据的数组
// @n 数组中数据个数
// 返回数据中 最大数的位数
int maxdigit(int data[],int n) // 最大的数有几位
{
int d= 1;
int p = 10;
for(int i=0;i<n;i++)
{
while(data[i]>=p)
{
p = p*10;
d++;
}
}
return d;
}
进行排序
最大数有几位，就需要几次循环
{
选中当前位进行排序，（复制到链表中）
将链表中的数据取出来放在数组中
}
// (data[j]/factor)%10 // 取这个数的最低位
void radixsort(int data[],int n)
{
int digits = maxdigit(data,n);
list<int> lists[10];
int d,j,k,factor;
for(d=1,factor=1;d<=digits;factor*=10,d++) // 排序几次
{
for(j=0;j<n;j++) // 将数据循环一遍，复制到链表中
{
lists[(data[j]/factor)%10].push_back(data[j]);
}
for(j=k=0;j<10;j++) // 将链表中的数据取出来放入数组中
{
while(!lists[j].empty())
{
data[k++] = lists[j].front();
lists[j].pop_front();
}
}
}
}
7.5 完整代码
#include <iostream>
#include <list>
using namespace std;
int maxdigit(int data[],int n) // 最大的数有几位
{
int d= 1;
int p = 10;
for(int i=0;i<n;i++)
{
while(data[i]>=p)
{
p = p*10;
d++;
}
}
return d;
}
void radixsort(int data[],int n)
{
int digits = maxdigit(data,n);
list<int> lists[10];
int d,j,k,factor;
for(d=1,factor=1;d<=digits;factor*=10,d++) // 排序几次
{
for(j=0;j<n;j++) // 将数据循环一遍，复制到链表中
{
lists[(data[j]/factor)%10].push_back(data[j]);
}
for(j=k=0;j<10;j++) // 将链表中的数据取出来放入数组中
{
while(!lists[j].empty())
{
data[k++] = lists[j].front();
lists[j].pop_front();
}
}
}
}
int main()
{
int data[10] = {179,208,306,93,859,984,55,9,271,33};
radixsort(data,10); // 基数排序
for(int i=0;i<10;i++)
cout<<data[i]<<" ";
cout<<endl;
cout << "Hello world!" << endl;
return 0;
}
参考
我见过最通俗易懂的快速排序过程讲解，转自《坐在马桶上看算法：快速排序》
