稳定性：在待排序的数据中，对于数值相同的数据，在整个排序过程中如果不会改变他们原来的先后顺序，则认为该排序算法是稳定的。
内排序：所有排序操作都在内存中完成。
外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行。
比较排序：在排序的最终结果里，元素之间的次序依赖于他们之间的比较。每个数都必须和其他数比较，才能确定自己的位置。比较排序适用于一切需要排序的情况。
常见的快速排序、归并排序、堆排序、冒泡排序等属于比较排序。
非比较排序：是通过确定每个元素之前，应该有多少个元素来排序。
常见的非比较排序有三种：桶排序、计数排序、计数排序。它们的时间复杂度都是O(n)。
一、冒泡排序（Bubble Sort）
数据左右比较，把较大的数据交换到右边，往后重复以上操作，直到把最大的数据交换到最后，特点是该算法对数据的有序性敏感，如果在一次的排序过程中没有发生一次交换，那么就意味着数据已经有序，可以立即停止排序。适合待排序的数据基本有序时，则冒泡的效率非常高
时间复杂度：平均：O(N^2) ，最优O:(N)。 稳定。
动图显示：
代码实现：
#define SWAP(a,b) {typeof(a) t=(a);(a)=(b);(b)=t;}
// 冒泡
void bubble_sort(TYPE* arr,size_t len)
{bool flag = true;
for(int i=len-1; i>0 && flag; i--)
{
flag = false;
for(int j=0; j<i; j++)
{
if(arr[j] > arr[j+1])
{
SWAP(arr[j],arr[j+1]);
flag = true;
}
}
}
}
二、选择排序（Selection Sort）
假定最开始的位置是最小值并记录下标min，然后与后面所有的数据比较，如果有比min位置的值更小的数，那么更新min，结束后min的下标与开始时发生过改变，才进行交换到开始位置。
虽然时间复杂度较高，但是数据交换次数比较少，因此实际的运行速度并不慢(数据交换比数据比较耗时)
时间复杂度：O(N^2) 不稳定
动图显示：
代码实现：
// 选择
void selection_sort(TYPE* arr,size_t len)
{
for(int i=0; i<len-1; i++)
{
int min = i;
for(int j=i+1; j<len; j++)
{
if(arr[j] < arr[min]) min = j;
}
if(i != min) SWAP(arr[i],arr[min]);
}
}
三、插入排序（Insertion Sort）
把数据看成两个部分，前部分是有序的，把剩余部分的数据逐个往前比较，如果比前面的数小，前面的数往后移动一位，继续往前比较，直到遇到更小的数，那么该数据的后一个位置即为可以插入的位置。适合对已经排序后的数据，新增数据后再排序
时间复杂度：O(N^2) 稳定
动图显示：
代码实现：
// 插入
void insertion_sort(TYPE* arr,size_t len)
{
for(int i=1,j=0; i<len; i++)
{
int val = arr[i]; // 要插入的数据
for(j=i; j>0 && arr[j-1] > val; j--)//j表示要插入的位置
{
arr[j] = arr[j-1];
}
if(j!=i) arr[j] = val;
}
}
四、希尔排序（Shell Sort）
是插入排序的增强版，由于插入排序时数据移动的步长较短，都是1，所以增加了增量的概念，通过不停地缩减增量，最终步长还是变回1，可以提高排序效率
当待排序数据远离最终位置时，希尔排序的效率高于插入排序
时间复杂度：O(NlogN)~O(N^2) 不稳定
演示：
代码实现：
// 希尔排序
void shell_sort(TYPE* arr,size_t len)
{
for(int k=len/2; k>0; k/=2) //k增量
{
for(int i=k,j=0; i<len; i++)
{
int val = arr[i];
for(j=i; j-k>=0 && arr[j-k] > val; j-=k)
{
arr[j] = arr[j-k];
}
if(j != i) arr[j] = val;
}
}
}
五、快速排序（Quick Sort）
在待排序数据中先找一个标杆位置p，备份p位置的值val，记录左标杆l、右标杆r，l从p的左边找比val大的数，找到后赋值给p位置，更新p到l，然后r从p的右边找比val小的数，找到后赋值给p位置，更新p到r
循环往复，直到l和r重合，把val还原回p位置完成一次快排，然后用同样的方式对p左右两边的数据进行快排
它的综合性能最优，因此得名快速排序，笔试时考的最多
时间复杂度：O(NlogN) 不稳定
动图演示：
代码实现void _quick(TYPE* arr,int left,int right{ if(left >= right) return; int l = left, r = right, p = left;
// 备份标杆的值
int val = arr[p];
while(l < r)
{
// 在p右边找比val小的数
while(r > p && arr[r] >= val) r--;
// r在p的右边找到比val小的数
if(r > p)
{
arr[p] = arr[r];
p = r;
}
while(l < p && arr[l] <= val) l++;
if(l < p)
{
arr[p] = arr[l];
p = l;
}
}
// 还原标杆的值
arr[p] = val;
_quick(arr,left,p-1);
_quick(arr,p+1,right);
}
// 快速排序
void quick_sort(TYPE* arr,size_t len)
{
_quick(arr,0,len-1);
}
六、堆排序（Heap Sort）（不稳定）
把待排序数据当做完全二叉树看待，先把二叉树调整成大顶堆结构，把根节点的值与末尾节点的值交换，然后数量范围-1，重新从上到下调整回大顶堆，继续以上操作，直到数量为1结束，此时全部数据就从小到大排序了
既可以顺序实现，也可以递归实现
时间复杂度：O(N*logN) 不稳定
动图演示：
代码实现：
public static void heapSort(int[] array) {
creatBigHeap(array);
int end = array.length - 1;
while (end > 0) {
swap(array, 0, end);
shiftDown(array, 0, end);
end--;
}
}
//建堆
public static void creatBigHeap(int[] array) {
for (int parent = (array.length - 1 - 1) / 2; parent >= 0 ; parent--) {
//调用向下调整
shiftDown(array, parent, array.length);
}
}
//向下调整的方法
public static void shiftDown(int[] array, int parent, int len) {
int child = (2 * parent) + 1;
while (child < len) {
if (child + 1 < len && array[child] < array[child + 1]) {
child++;
}
if (array[child] > array[parent]) {
swap(array, child, parent);
parent = child;
child = 2 * parent + 1;
}else {
break;
}
}
}
//交换的方法
public static void swap(int[] array, int i, int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
七、归并排序（Merge Sort）（稳定）
首先需要把数据拆分成单独的个体，然后按照从小到大的顺序比较后排序到一段临时空间中，把排序后的临时空间中的数据拷贝回原内存，然后依次把有序的个体继续以上操作合并成更大的有序部分。归并排序不需要交换数据，减少了交换的耗时，但是需要额外的存储空间，是一种典型的以空间换时间的算法
时间复杂度：O(N*logN) 稳定的
动图演示：
代码实现：
// 合并 l左部分最左 p左部分最右 p+1右部分最左 r右部分最右
void __merge(TYPE* arr,TYPE* temp,int l,int p,int r)
{
// 合并前 左右部分各自有序
if(arr[p] <= arr[p+1]) return;
int s = l;
int i = l, j = p+1;
while(i<=p && j<=r)
{
// 左右部分从开头进行比较
if(arr[i] <= arr[j]) // <= 确保是稳定的
temp[s++] = arr[i++];
else
temp[s++] = arr[j++];
}
// 比完后，把多的部分剩余的数据依次存入temp
while(i<=p) temp[s++] = arr[i++];
while(j<=r) temp[s++] = arr[j++];
// 把temp还原回对应位置的arr
memcpy(arr+l,temp+l,sizeof(TYPE)*(r-l+1));
}
// 拆分
void _merge(TYPE* arr,TYPE* temp,int l,int r)
{
if(l >= r) return;
int p = (l+r)/2;
_merge(arr,temp,l,p);
_merge(arr,temp,p+1,r);
// 合并
__merge(arr,temp,l,p,r);
}
// 归并排序
void merge_sort(TYPE* arr,size_t len)
{
// 申请临时存储空间
TYPE* temp = malloc(sizeof(TYPE)*len);
_merge(arr,temp,0,len-1);
free(temp);
}
八、计数排序（Counting Sort）（非比较、稳定）
找出待排序数据中的最大、最小值，创建长度为最大值-最小值+1 的哈希表，根据哈希函数 数据-最小值 当做哈希表的下标并对所有数据做标记，然后从头遍历哈希表，当某个位置的值大于0，把该位置的下标+最小值的到结果依次放回原数据内存中
是一种典型的以空间换时间的算法
理论上该算法的速度是非常快的，它不是基于比较的排序算法，在一定范围内的整数排序中快于任意一种基于比较的排序算法，但是有很大的局限性，只适合整型数据排序，数据的差值不宜太大，否则会非常浪费内存，反之数据差值不大、重复数比较多的情况下性价比很高
时间复杂度：Ο(n+k)（其中k是整数的范围） 稳定的
动图演示：
代码实现：
// 计数排序
void count_sort(TYPE* arr,size_t len)
{
TYPE max = arr[0],min = arr[0];
for(int i=1; i<len; i++)
{
if(arr[i] > max) max = arr[i];
if(arr[i] < min) min = arr[i];
}
TYPE* temp = calloc(sizeof(TYPE),max-min+1);
for(int i=0; i<len; i++)
{
temp[arr[i]-min]++;
}
for(int i=0,j=0; i<max-min+1; i++)
{
while(temp[i]--) arr[j++] = i+min;
}
free(temp);
}
九、桶排序（Bucket Sort）
一般是把数据根据数值分到不同的"桶"，通过不同的、合适的其他排序算法对"桶"中的数据进行排序，然后再把各个"桶"的数据依次拷贝回原内存中]
桶排序是一种降低排序规模的排序思想，也是以空间换时间的算法（非比较）
缺点：如何分桶、桶如何定义，都需要针对具体待排序的数据进行分析后才能确定
桶排序的稳定性取决于桶内排序使用的算法
最佳情况：T(n) = O(n+k) 最差情况：T(n) = O(n+k) 平均情况：T(n) = O(n2)
有些资料上认为桶排序可以做到稳定，所以认为桶排序稳定
代码实现：
// cnt桶数 range桶中数据的差值
void _bucket(TYPE* arr,size_t len,int cnt,TYPE range)
{
// 申请桶内存
// bucket_s指向桶的开头位置
// bucket_e指向桶的末尾 接下去要入桶的位置
TYPE* bucket_s[cnt],*bucket_e[cnt];
for(int i=0; i<cnt; i++)
{
// 数据有可能全在一个桶内
bucket_s[i] = malloc(sizeof(TYPE)*len);
bucket_e[i] = bucket_s[i];
}
// 把数据按照对应的范围放入对应的桶中
for(int i=0; i<len; i++)
{
for(int j=0; j<cnt; j++)
{
if(j*range <= arr[i] && arr[i] < (j+1)*range)
{
*(bucket_e[j]) = arr[i];
bucket_e[j] += 1;
break;
}
}
}
// 通过其他排序对各个桶中的数据排序
for(int i=0; i<cnt; i++)
{
// 计算桶中元素的数量
int size = bucket_e[i] - bucket_s[i];
// 其他排序
if(1 < size)
bubble_sort(bucket_s[i],size);
// 按照先后顺序 放入原内存中
memcpy(arr,bucket_s[i],size*sizeof(TYPE));
arr += size;
free(bucket_s[i]);
}
}
// 桶排序
void bucket_sort(TYPE* arr,size_t len)
{
_bucket(arr,len,4,25);
}
十、基数排序（Radix Sort）(非比较、稳定)
基数排序也是非比较的排序算法，对每一位进行排序，从最低位开始排序，复杂度为O(kn),为数组长度，k为数组中的数的最大的位数；
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的
最佳情况：T(n) = O(n * k) 最差情况：T(n) = O(n * k) 平均情况：T(n) = O(n * k)
动图演示：
代码实现：
// 基数排序
void radix_sort(TYPE* arr,size_t len)
{
ListQueue* queue[10] = {};
for(int i=0; i<10; i++)
{
queue[i] = create_list_queue();
}
// 循环次数由最大值的位数决定
TYPE max = arr[0];
for(int i=1; i<len; i++)
{
if(arr[i] > max) max = arr[i];
}
// i是1表示处理个位，2表示处理十位...
for(int i=1,k=1; max/k>0; k*=10,i++)
{
int mod = pow(10,i);
int div = mod/10;
for(int j=0; j<len; j++)
{
// 获取arr[j] 某位的数
int index = arr[j]%mod/div;
push_list_queue(queue[index],arr[j]);
}
// 对所有队列依次出队回原内存中
for(int j=0,i=0; j<10; j++)
{
while(!empty_list_queue(queue[j]))
{
arr[i++] = head_list_queue(queue[j]);
pop_list_queue(queue[j]);
}
}
}
for(int i=0; i<10; i++)
{
destroy_list_queue(queue[i]);
}
}
标签：arr,int,len,算法,array,排序,TYPE From： https://www.cnblogs.com/ljf-0804/p/17607030.html