2020-06-21
思想
#
大停，小停，大小交换，相遇时相遇点和基准点交换，以相遇点为界限展开递归
1、选取一个基准元素（star）
2、比star小的放到star左边，比star大的放到star右边
3、当上述步骤执行完成后，star的位置就不变了，它现在的位置就是它最终该放置的位置
4、对star左边所有元素进行1、2操作，对star右边元素进行1、2操作
代码实现
#
#include "sort.h"
static void swap(int *, int, int);
static void sort1(int *, int, int);
void sort(int *arr, int len)
{
sort1(arr,0, len - 1);
}
/*
大停，小停，大小交换，相遇时相遇点和基准点交换，以相遇点为界限展开递归
*/
static void sort1(int *arr, int start, int end)
{
if (start >= end)
{
return;
}
int star = arr[start];
int l = start, r = end;
while (l < r)
{
while ((arr[r] > star) && (l < r))
{
r--;
}
while ((arr[l] <= star) && (l < r))
{
l++;
}
if (l < r)
{
swap(arr, l, r);
}
else
{
swap(arr, start, l);
}
}
sort1(arr, start, l -1);
sort1(arr, l + 1, end);
}
static void swap(int *arr, int num1, int num2)
{
int temp = arr[num1];
arr[num1] = arr[num2];
arr[num2] = temp;
}
复杂度
#
平均时间复杂度：O(nlog₂n)
空间复杂度：O(log₂n)
不稳定的排序算法
2020-06-21
思想
#
1.将序列元素先分割成一个个单独的元素，由于只有一个元素，我们可以看作它是有序的
2.将上述的序列两两合并，并使得他们合并后的结果仍然有序
3.重复上述步骤，直到合成一个完整的序列
从实现上来看，有点像二叉树的后序遍历。
代码实现
#
public void mergeSort(int[] a,int low,int high){
//可以看到，当切割到只剩一个元素时，开始进行合并
if(low<high){
//找到数组中的中间点，把数组分为两部分
int mid=(low+high)/2;
//对左边进行mergeSort操作
mergeSort(a,low,mid);
//对右边进行mergeSort操作
mergeSort(a,mid+1,high);
//合并左右两部分
merge(a,low,mid,high);
}
}
void merge(int[] a,int low,int mid,int high){
for(int i=low;i<=high;i++){
//缓冲空间，
buf[i]=a[i];
}
//i，j分别是左指针和右指针
int i,j,k;
//比较左右两边的元素，谁小谁放在前面
for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){
if(buf[i]<=buf[j])
a[k]=buf[i++];
else if(buf[i]>buf[j])
a[k]=buf[j++];
}
//当一边全部比较完成后，另一边的元素就直接送到a的后面
while(i<=mid)
a[k++]=buf[i++];
while(j<=high)
a[k++]=buf[j++];
}
复杂度
#
时间复杂度：O(nlogn)
空间复杂度：O(n)
稳定的排序算法
2020-06-21
思想
#
第一趟从n个无序记录中选择关键字最小的记录与第1个记录交换，此时第一个记录为有序
第二趟从第二个记录开始的n-1个无序记录中选择关键字最小的与第2个记录交换，此时前两个记录有序
……
如此下去，直到无序序列只剩最后一个元素，排序结束
代码实现
#
public void selectSort(int[] a) {
for(int i=0;i<a.length;i++){
//记录最小元素的位置
int min=i;
//该循环来寻找最小元素的位置
for(int j=i+1;j<a.length;j++){
if(a[j]<a[min]){
min=j;
}
}
//交换第i个元素和最小元素
int temp=a[i];
a[i]=a[min];
a[min]=temp;
}
}
复杂度
#
时间复杂度：O(n²)
空间复杂度：O(1)
稳定的排序算法
2020-06-21
思想
#
特点是两两交换。
相邻的两个数比较，每次比较将大的数放到下面，一次循环后， 最大的数就在最下面了。
小数上冒，大数沉底。
经过第一趟排序后，最大的数就移到了最后面。
第二趟排序会将次大值移到倒数第二位。
以此类推，直到所有的数排好位置。
代码实现
#
#include <stdio.h>
void sort(int *a, int length);
int main()
{
int n[10] = {9, 4, 10, 43, 75, 14, 0, 12, 53, 71};
sort(n, 10);
for (int i = 0; i < 10; i++)
{
printf("a[%d] is %d\n", i, n[i]);
}
return 0;
}
void sort(int *a, int length)
{
for(int i = 0; i < length; i++)
{
for(int j = 1; j < length; j++)
{
if(a[j - 1] > a[j])
{
int tmp = a[j - 1];
a[j - 1] = a[j];
a[j] = tmp;
}
}
}
}
复杂度
#
时间复杂度：O(n²)
空间复杂度：O(1)
稳定的排序算法
2020-06-21
直接插入排序
#
思想
#
将记录集合分为有序和无序两部分，每次从无序序列中取一个记录加入有序序列中，使该有序序列仍然有序。重复该步骤，直到无序序列中的记录全部插入有序序列。
代码实现
#
public static void insertionSort(int[] a){
for(int i=1;i<a.length;i++){
int key=a[i];//记录当前i位置的值
int j=i-1;
//将大于key的值全部后移
while(j>=0&&a[j]>key){
a[j+1]=a[j];
j--;
}
a[j+1]=key;
}
}
复杂度
#
时间复杂度：O(n²)
空间复杂度：O(1)
稳定的排序算法
折半插入排序
#
思想
#
在将无序序列中的元素插入有序序列时，采用折半查找确定其位置，从而减少查找的次数
代码实现
#
for(int i=1;i<a.length;i++){
int key=a[i];
int low=0,high=i-1;
//加入一个折半查找，减少查找次数
while(low<=high){
int mid=(low+high)/2;
if(a[mid]>key)
high=mid-1;
else if(a[mid]<key)
low=mid+1;
}
int j;
for(j=i-1;j>=high+1;j--)
a[j+1]=a[j];
a[j+1]=key;
}
复杂度
#
与直接插入排序相同
2020-06-21
定义
#
节点均小于其左孩子节点和右孩子节点
左孩子节点均小于其左右孩子节点
右孩子节点均小于其左右孩子节点
……
代码实现
#
public void buildHeap(int[] n,int len){//建立初始堆
for(int i=len/2;i>=1;i--){
adjustHeap(n,i,len);
}
}
public void adjustHeap(int[] n,int s,int len){//调整堆
for(int i=2*s;i<=len;i*=2){
//如果出现左右孩子节点大于该s节点时，该位置无需调整
//否则，不仅需要调整该s节点，还需要进行向下调整
if(i<len&&n[i]>n[i+1])
i++;
if(n[s]<n[i])
break;
else{
n[0]=n[i];
n[i]=n[s];
n[s]=n[0];
s=i;
}
}
}
public void heapSort(int[] n,int len){//堆排序
for(int i=len;i>1;i--){
//将堆顶元素与最后一个元素调换位置
n[0]=n[i];
n[i]=n[1];
n[1]=n[0];
//将未排序的前i-1个元素重新调整为堆
adjustHeap(n,1,(i-1));
}
}
复杂度
#
建立堆的时间复杂度：O(n)
堆排序的时间复杂度：O(nlogn)
空间复杂度：O(1)
不稳定的排序算法
2020-06-21
思想
#
- 先将整个待排序列中的记录按照指定的下标进行分组，并对每个组内的记录采用直接插入法排序
- 然后依次减少下标量，即使每组包含的记录增多，再继续对每组组内的记录采用直接插入法排序
- 依此类推，当下标增量减少到1时，整个待排序记录序列已成为一组，但由于此前所做的直接插入排序工作，整个待排序记录序列已经基本有序，最终完成了排序
代码实现
#
for(int dk=n.length/2;dk>=1;dk=dk/2){ //增量因子
for(int i=dk;i<n.length;i++){ //下面的代码类似插入排序
if(n[i]<n[i-dk]){
int temp=n[i];
int j;
//比temp大的往后挪，直到遇到比temp更小的
for(j=i-dk;j>=0&&temp<n[j];j=j-dk)
n[j+dk]=n[j];
n[j+dk]=temp;//将temp放在停的位置上
}
}
}
复杂度
#
时间复杂度：O(n²)
空间复杂度：O(1)
不稳定的排序算法