排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序。
常见的排序算法：冒泡、快排、插入、希尔、选择、堆排、归并。
1、冒泡排序
原理：一个无序数组，按照升序排列。int i 代表循环的次数，int j 代表数组的下标，if(arr[j]>arr[j+1]),交换位置，依次类推。每循环一次，一个数字在它相应的位置。
源码：
计算
安全
数据库
网络和加速
企业服务
void Bubble_sort(int arr[],int len)
{
int i;
for(i=0;i<len;i++)
{
int j;
for(j=0;j<len-1-i;j++)
{
if(arr[j]>arr[j+1])
{
int tmp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=tmp;
}
}
}
}时间复杂度o(n^2),空间复杂度o(1).
2、快排：
原理：从中间向两边的探索，在序列中选择一个准基数，用来做参考的数，选择左边的第一个数为例，将序列中所有大于准基数的数放在它的右边，小于的放在它的左边，最终确定准基数的位置。
定义两个变量left、right，可以将其看作指针，指定其对应的某元素，一个指向最左边，一个指向最右边，选择left作为准基数，从最左边的数和它比较，当准基数小于right指向的数时，right--，如果大于right指向的数，arr[left]=arr[right],当准基数大于左边的值时，left++，如果小于左边的值，arr[right]=arr[left],最后将准基数放在其正确的位置，然后重复上述步骤递归。
源码：
void Quick_sort(int arr[],int Front,int Back)
{
int left=Front;
int right=Back;
if (left < right)
{
int tmp = arr[left];
while(left<right)
{
while (left < right && tmp < arr[right])
{
right--;
}
arr[left] = arr[right];
while (left < right && tmp > arr[left])
{
left++;
}
arr[right] = arr[left];
}
arr[left] = tmp;
Quick_sort(arr,Front,left-1);
Quick_sort(arr,left+1,Back);
}
}时间复杂度o(nlog2n),空间复杂度o(nlog2n)
3、插入排序：
原理：插入排序就是讲一个数字插入到它本该占据的位置。
源码：
void Insertsort(int arr[],int len)
{
int i = 0;
for (i = 0; i < len-1; i++)
{
int tmp = arr[i+1];
int pos = i;
while (pos>=0 && arr[pos] > tmp)
{
arr[pos+1] = arr[pos];
pos--;
}
arr[pos+1] = tmp;
}
}4、希尔排序
原理：希尔排序就是基于插入排序的一种改进，先将整个待排元素分成若干个子序列（有相隔某个增量元素组成），分别进行插入排序，然后缩减增量再进行排序，待这整个元素基本有序时（增量足够小），再对全体元素进行一次插入排序。
源码：
void ShellSort(int arr[], int len)
{
int gap = len;
while (gap)
{
gap = gap/2;
for (int i = gap; i < len; i++)
{
int tmp = arr[i];
int pos = i-gap;
while (pos>=0 && arr[pos] > tmp)
{
arr[pos+gap] = arr[pos];
pos-=gap;
}
arr[pos+gap] = tmp;
}
}
}时间复杂度o(n^2),空间复杂度o(1).
5、选择排序
原理：在待排序列中将第一个元素记为最小的，第一个位置记为最小位置，在剩余所有元素中找到最小的与之交换。
源码：
void SelectSort(int arr[], int len)
{
for (int i = 0; i < len; i++)
{
int min = arr[i];
int index = i;
for (int j = i+1; j < len; j++)
{
if(arr[j] < min)
{
min = arr[j];
index = j;
}
}
arr[index] = arr[i];
arr[i] = min;
}
}时间复杂度o(n^2),空间复杂度o(1).
6、堆排
将初始化序列构成大堆，此堆为初始的无序区，将堆顶元素与最后一个元素交换位置，得到一个无序区和一个有序区，交换后的堆顶元素不变，因此将堆顶元素向下调整，保证最大堆的性质。
源码：
void HeapDown(int arr[],int i,int len)
{
int parent=i;
int child=2*i+1;
while (child < len)
{
if(child+1<len && arr[child]<arr[child+1])
{
child=child+1;
}
if(arr[child]>arr[parent])
{
swap(arr[parent],arr[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void CreateHeap(int arr[],int len)
{
int i=0;
for(i=len/2-1;i>=0;i--)
{
HeapDown(arr,i,len);
}
}
void HeapSort(int arr[],int len)
{
CreateHeap(arr,len);
for (int i = len-1; i >= 0; i--)
{
swap(arr[0],arr[i]);
HeapDown(arr,0,i);
}
}时间复杂度o(nlog2n),空间复杂度o(1).
7、归并排序
源码：
void MergeArray(int arr[], int low, int mid, int high,int a[])
{
int i = low;
int j = mid+1;
int k = 0;
while (i <= mid && j <= high)
{
if (arr[i] <= arr[j])
{
a[k] = arr[i];
i++;
k++;
}
else
{
a[k] = arr[j];
j++;
k++;
}
}
while (i<=mid)
{
a[k] = arr[i];
i++;
k++;
}
while (j <= high)
{
a[k] = arr[j];
j++;
k++;
}
for (i = 0; i < k; i++)
{
arr[low+i] = a[i];
}
}
void MSort(int arr[],int first, int last, int a[])
{
if(first < last)
{
int mid = (first+last)/2;
MSort(arr,first,mid,a);
MSort(arr,mid+1,last,a);
MergeArray(arr,first,mid,last,a);
}
}
void Mergesort(int arr[], int sz)
{
int *a = new int[sz];
MSort(arr,0,sz-1,a);
delete []a;
}时间复杂度o(nlog2n),空间复杂度o(n)。
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
