排序《数据结构》

1.排序的概念及其运用

1.1 排序的概念

1、排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
2、稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
3、 内部排序：数据元素全部放在内存中的排序。
4、外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不断地在内外存之间移动数据的排序。

1.2 排序运用

1.3常见的排序算法

1.4 排序动图演示

插入排序

void InsertSort(int* a,int n)//n为数组大小

希尔排序

void ShellSort(int* a,int n)//n为数组大小

选择排序

void SelectSort(int*a, int n);//n为数组大小

堆排序

voidAdjustDwon(int*a, int n, int parent);//向下调整
{
// 先假设左孩子小
int child = parent * 2 + 1;while (child < n)  // child >= n说明孩子不存在，调整到叶子了
{// 找出小的那个孩子if (child + 1 < n && a[child + 1] < a[child]){++child;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}
}
}
voidHeapSort(int*a, int n);

快排

void QuickSort(int* a,int n);

2.常见排序算法的实现

2.1 插入排序

基本思想：
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，
直到所有的记录插入完为止，得到一个新的有序序列。

根据以上文字：
我们可以用（玩扑克牌来实例化）

当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移

插入排序特性总结：
1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定

插入排序的实现

void InsertSort(int* a,int n)
{
for(int i=0;i<n-1;i++)//多趟
//一趟插入排序{
int end=i;
int tmp=a[end+1];
while(end>=0){if(a[end]>tmp){a[end+1]=a[end];end--;}elsebreak;//以防tmp是数组中最小的数}
a[end+1]=tmp;}}

2.2希尔排序

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

希尔排序的特性总结：1. 希尔排序是对直接插入排序的优化。2. 当gap > 1时都是预排序，目的是让数组更接近于有序。 当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
3.  希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定：大概是n^(1.3)

4. 稳定性：不稳定

void ShellSort(int* a,int n)
{
while(gap>1){// +1保证最后一个gap一定是1// gap > 1时是预排序// gap == 1时是插入排序int gap=(3/n)+1;//第一趟for(int i=0;i<n-gap;i++){int end=i;int tmp=a[end+1];while(end>=0){if(a[end]>tmp){a[end+1]=a[end];end-=gap;}elsebreak;}a[end+1]=tmp;}}}

2.3 快排

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

特点总结：

快速排序的特性总结：
快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
时间复杂度：O(N*logN)
空间复杂度：O(logN)
稳定性：不稳定

1、hoare版本

void QuickSort(int*a,int left,int right)
{if(right<=left){return ;}int begin=lef;int keyi=left;int end=right;while(begin<end){while(begin<end&&a[keyi]<=a[begin]){begin++;}while(begin<end&&a[keyi]>=a[end]){end--;}Swap(&a[begin],&a[end]);//交换
}
Swap(&a[begin],a[keyi]);
keyi=begin;
QuickSort(a,left,keyi-1);
QuickSort(a,keyi+1,right);
}

左边做keyi，右边先走，可以保证相遇位置比keyi小

相遇场景分析：
L遇R: R先走,停下来，那么R停下的条件是比keyi小的位置,
L没找到大的，遇到R停下来了

 R遇L:

那么我们可以得出：keyi在左边，R先走，keyi在右边，L先走

2、挖坑法

3、双指针表达法

代码实现：

int partSort1(int* a, int left, int right)//双指针排序法
{int prve = left;int cur = prve + 1;int keyi = left;while (cur <= right){if (a[keyi] < a[cur] && ++prve != cur){Swap(&a[prve], &a[cur]);cur++;}cur++;}Swap(&a[prve], &a[keyi]);return prve;
}
void QuickSort(int* a, int left, int right)
{if (left >= right){return;}if ((right - left + 1) < 10){insertSort(a + left, right - left + 1);}else{int keyi = partSort1(a, left, right);QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);}
}

2.4 快速排序优化

1. 三数取中法选key

int order(int* a, int left, int right)
{int midi = (left + right) / 2;if (a[left] > a[midi]){if (a[midi] > a[right]){return midi;}else if (a[left] > a[right]){return right;}else{return left;}}else if(a[midi]<a[right]){return midi;}else{if (a[left] < a[right]){return right;}elsereturn left;}}

2. 递归到小的子区间时，可以考虑使用插入排序

void insertSort(int* a, int n)
{for (int i = 0;i < n-1;i++){int end=i;int tmp = a[end+1];while (end >= 0){if (a[end] > tmp){a[end + 1] = a[end];end--;}else{break;}}a[end + 1] = tmp;}
}void QuickSort(int* a, int left, int right)
{if (left >= right){return;}if ((right - left+1) < 10)//小区间优化{insertSort(a+left, right - left + 1);}else{int midi = order(a, left, right);Swap(&a[midi], &a[left]);int keyi = left;int begin = left, end = right;while (begin < end){while (begin < end && a[end] >= a[keyi]){--end;}while (begin < end && a[begin] <= a[keyi]){++begin;}Swap(&a[begin], &a[end]);}Swap(&a[begin], &a[keyi]);keyi = begin;QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);}
}

快排（非递归）

用栈来代替递归

 先把区间left和right入栈，然后分隔区间，在令分隔的右区间先入栈，左区间后入栈（因为栈后进先出的原则），那么弹出来的就是左区间下标，在对坐下标进行处理，每一次出栈都代表着区间排序，
等栈为空时，那么排序就完成了

void QuickSortNonR(int* a, int left, int right)
{
ST st;
STInit(&st);
STPush(&st, right);//进栈
STPush(&st, left);//进栈
while()
left = STTop(&st);
STPop(&st);
right= STTop(&st);
STPop(&st);
int begin = left;
int end = right;
int keyi = begin;
while (begin < end)//交换
{while (begin < end && a[end] >= a[keyi]){end--;}while (begin < end && a[begin] <= a[keyi]){begin++;}Swap(&a[begin],&a[end]);
}
Swap(&a[keyi], &a[begin]);keyi = begin;
// [left, keyi-1] keyi [keyi+1, right]
if (keyi + 1 < right ){STPush(&st, right);//右区间的右下标（入栈）STPush(&st, keyi + 1);//右区间的左下标（入栈）}if (left < keyi - 1){STPush(&st, keyi - 1);//左区间的右下标（入栈）STPush(&st, left);//左区间的坐下标（入栈）}}STDestroy(&st);
}

2.6堆排序

直接选择排序的特性总结：
堆排序使用堆来选数，效率就高了很多。
时间复杂度：O(N*logN)
空间复杂度：O(1)
稳定性：不稳定

实现代码：

void headsport(int* arr, int n)
{//时间复杂度O(N)for (int i = (n-1-1)/2;i >=0;i--){AdjustDown(arr,n,i);//向下调整建堆}int end = n - 1;//取最后一位数据while (end > 0)
{Swap(&arr[0], &arr[end]);//交换AdjustDown(arr, end, 0);//在向下建堆end--;}
}

2.7 归并排序

基本思想
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and
Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有
序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：

特性总结：

 1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。2. 时间复杂度：O(N*logN)3.  空间复杂度：O(N)4.  稳定性：稳定

代码实现:

void _mergeSort(int* a, int* tmp ,int begin, int end)
{if (end-begin<1){return;}int mid = (begin + end) / 2;//如果[begin,mid-1],[mid,end]有序就归并_mergeSort(a, tmp, begin, mid);_mergeSort(a, tmp, mid+1, end);//归并int begin1 = begin;int begin2 = mid+1;int end1 = mid;int end2 = end;int i = begin;while (begin1<=end1&&begin2<=end2){if (a[begin1] < a[begin2]){tmp[i++] = a[begin1++];}elsetmp[i++] = a[begin2++];}while (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}memcpy(a+begin, tmp+begin,(end-begin+1)*sizeof(int));
}void mergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}_mergeSort(a, tmp, 0, n - 1);
}

排序部分结束啦！！！感谢大家观看