1.冒泡排序算法
void paixu(int legth, int arr[])
{
int flag = 1; //flag=1表示数组否发生改变
while(legth-- && flag)
{
flag = 0; // 没有发生改变
for (int i = 0; i<length; i++)
{
if ( arr[i+1] < arr[i] )
{
flag = 1; // 数组发生改变位置交换
int temp = arr[i + 1];
arr[i + 1] = arr[i];
arr[i] = temp;
}
}
}
}
2.选择排序
基本思想还是冒泡排序。每一轮找到最小值后和第一个元素进行交换,依次类推
void paixu(int arr, int leghth)
{
for(int i=0; i<legrh; i++)
{
int k = i;
for(int j=i; j<length; j++)
{
if(arr[j] < arr[k])
{
k = j;
}
}
swap(arr[i],arr[k]);
}
}
3.插入排序
优点是当原始序列基本有序时,再将一个新的数据插入进来比较方便,也比较高效率。
void insertsort(int arr[], int legth)
{
for(int i=1; i<legth; i++)
{
for(int j=i; j>=1; &&arr[j]<arr[j-1];j--)
{
swap(arr[j],arr[j-1]);
}
}
}
4.希尔排序
优化版的插入排序
void shellSort(int arr[], int legth)
{
int h=4;
int h=1;
int t = legrh / 3;
while(h<t) h= 3*h+1;
while (h>=1)
{
for(int i=h; i<legth; i++)
{
for(int j=i; j>=h; &&arr[j]<arr[j-h]; j-h)
{
swap(arr[j],arr[j-h]);
}
h/=3;
}
}
经典的希尔序列 : 1 , 4 , 16, …, 3*n+1
5.快速排序
冒泡排序的优化版本。核心思想:使用轴,每一轮左右递归后,把轴放在中间,使得轴的左边都比较小,轴的右边都比轴打。当所有的递归都结束后就自然拍好序列。
void quickSort(int arr[], int left, int right)
{
if(left>=right) return;
int i=left;
int j=right;
int pivot = arr[i];
while(i<j)
{
while(i<j&&arr[j]>=pivot) j--;
arr[i] = arr[j];
while(i<j && arr[i]<=pivot) i++;
arr[j] = arr[i];
}
arr[i] = pivot;
quickSort(arr, left, i-1);
quickSort(arr, i+1, right);
}
6.归并排序
基于分而治之的思想。拿两个有序的序列重新组合成一个新的有序序列。
void guibing(int arr1[], int arr2[], int alen, int blen, int *temp)
{
int i = 0;
int j = 0;
int k = 0;
while(i<alen&&b<blen){
if(a[i]<b[j])
{
temp[k] = a[i];
k++;
i++;
}
else
{
temp[k] = b[j];
k++;
j++;
}
while(i<alen)
{
temp[k] = a[i];
k++;
i++;
}
while(j<blen)
{
temp[k] = b[j];
k++;
j++;
}
}
}
当只有一个序列的时候采用归并排序
void merge(int arr[], int low, int mid, int height, int *temp)
{
int i=low;
int j=mid+1;
int k = low;
while(i<=mid&&j<=height)
{
temp[k++] = arr[i] < arr[j] ? arr[i++]: arr[j++];
}
while (i<= mid)
{
temp[k++] = arr[i++];
}
while (j<= height)
{
temp[k++] = arr[j++];
}
for(i = low; i<height; i++)
{
arr[i] = temp [i];
}
}
void merge_sort(int arr[], int low, int height, int *temp)
{
if(low >= height)
{
return;
}
int mid = low + (height - low)/2; // (low + height ) /2
merge_sort(arr, low, mid, temp);
merge_sort(arr, mid + 1, height, temp);
merge(arr, low, height, temp);
}
7.堆排序
外堆:
需要申请和原来数组长度大小的内存空间,这段内存空间用来存储堆结够。
内堆:
不需要重新申请内存,直接在原来的数组上进行排序
堆结构本质上是一个完全二叉树。每一个存储的节点都是连续的。
知道当前下标为current,则其左子树下标为2current+1,其右子树下标为2current+2(从零开始),
如果从1开始计数左子树下标为2current,其右子树下标为2current+1。
大顶堆:父亲的权值比左右子树的权值大。
小顶堆:父亲的权值比左右子树的权值小。
外堆实现
typedef struct Heap
{
int *root;
int length;
}Heap;
Heap *creatHeap(int length)
{
Heap *heap = (Heap*)malloc(sizeof(heap));
assert(heap); //检查是否为真
Heap->length = 0;
heap->root = (int *)malloc(sizeof(int)*length);
assert(heap->root);
return heap;
}
//入堆
void pushHeap(Heap *heap, int data)
{
int current = heap->length++;
int parent = current / 2;
heap->root[heap->length++] = data;
heap->root[current] = data;
while(parent!=current){
if(heap->root[current]<heap->root[parent])
{
swap(arr, current, parent);
current = parent;
parent = current/2;
}
else break;
}
}
//出堆
int popHeap(Heap *heap)
{
int val = heap->root[0];
int current = 0;
int rchild = 2*current +2 ;
int small;
int n = --heap->length;
heap->root[--heap->length];
while(rchild<=heap->length){
small = heap->root[rchild - 1] < heap->root[rchild]?rchild-1 : rchild;
if(heap->root[small]<heap->root[current])
{
swap(heap->root,small,current);
current = samll;
rchild = 2 * current+2;
}
}
return val;
}
内堆 大顶堆
void heapify(int arr[], int length, int current)
{
int rchild = 2*current+2;
int large;
while(rchild <= length)
{
large = rchild == length?rchild-1:(arr[rchild-1] > arr[rchild]?rchild - 1 : rchild);
if(arr[large]>arr[current])
{
swap(arr, large, current);
current = large;
rchild = 2*current+2;
}
else break;
}
}
void heapSort2(int arr[], int length)
{
int current = length / 2;
while(current >=0){
heapify(arr, length, current);
current --;
while(length>0)
{
swap(arr,0,length-1);
length--;
heapify(arr, length, 0);
}
}
}
8.计数排序
算法思想:统计原来数组的数据, 并将数据转换成下标存储于一个临时的空间中,然后变量临时空间把对应的下标值放回原数组中,当便厉临时空间完成后,原来数组也排好序了。类似于哈希表
void countSort(int arr[], int length)
{
for(int i = 0; i < length; i++)
{
temp[arr[i]]++;
}
for(int i=0n j=0; i<N; i++)
{
while(temp[i]--)
arr[j++] = i;
}
}
9.基数排序
举例:
154 423 365 251 78 92 640
个位十位百位去比较
第一轮(个位):640 251 92 423 154 365 78
第二轮(十位):423 640 251 154 365 78 92
第三轮(百位):78 92 145 251 365 423 640
// === File: radix_sort.cpp ===
/* 获取元素 num 的第 k 位,其中 exp = 10^(k-1) */
int digit(int num, int exp) {
// 传入 exp 而非 k 可以避免在此重复执行昂贵的次方计算
return (num / exp) % 10;
}
/* 计数排序(根据 nums 第 k 位排序) */
void countingSortDigit(vector<int> &nums, int exp) {
// 十进制的位范围为 0~9 ,因此需要长度为 10 的桶
vector<int> counter(10, 0);
int n = nums.size();
// 统计 0~9 各数字的出现次数
for (int i = 0; i < n; i++) {
int d = digit(nums[i], exp); // 获取 nums[i] 第 k 位,记为 d
counter[d]++; // 统计数字 d 的出现次数
}
// 求前缀和,将“出现个数”转换为“数组索引”
for (int i = 1; i < 10; i++) {
counter[i] += counter[i - 1];
}
// 倒序遍历,根据桶内统计结果,将各元素填入 res
vector<int> res(n, 0);
for (int i = n - 1; i >= 0; i--) {
int d = digit(nums[i], exp);
int j = counter[d] - 1; // 获取 d 在数组中的索引 j
res[j] = nums[i]; // 将当前元素填入索引 j
counter[d]--; // 将 d 的数量减 1
}
// 使用结果覆盖原数组 nums
for (int i = 0; i < n; i++)
nums[i] = res[i];
}
/* 基数排序 */
void radixSort(vector<int> &nums) {
// 获取数组的最大元素,用于判断最大位数
int m = *max_element(nums.begin(), nums.end());
// 按照从低位到高位的顺序遍历
for (int exp = 1; exp <= m; exp *= 10)
// 对数组元素的第 k 位执行计数排序
// k = 1 -> exp = 1
// k = 2 -> exp = 10
// 即 exp = 10^(k-1)
countingSortDigit(nums, exp);
}