21-数据结构-内部排序-交换排序

        简介：主要根据两个数据进行比较从而交换彼此位置，以此类推，交换完全部。主要有冒泡和快速排序两种。

目录

一、冒泡排序

1.1简介：

1.2代码：

二、快速排序

1.1简介：

1.2代码：

一、冒泡排序

1.1简介：

        冒泡，即每次给表中一个数据，弄到最前面或者最后面，以此类推。其主要思想为：外循环是趟数，内循环是比较次数，两两比较，一点点往后冒。从第1趟比较开始比较，比较n-1次，第2趟比较，比较n-2次，以此类推，所以比较次数为

每个框框表示一趟的比较，从头，两两比较。后面我设置了flag验证是否还需要再跑趟次了，避免做无用功，如果有序了，则不需要比较

        空间复杂度O(1)

        时间复杂度O()

        稳定性：两两交换，很稳定。

1.2代码：

#include <stdio.h>
void BubbleSort(int *a,int n)
{int i,j,flag;for(i=0;i<n-1;i++)//比较趟数，每趟都从头到尾（n-1-i）进行比较遍历，给一个数冒到后面，冒完的，下一轮就不参与比较了 {flag=1;//避免做无用功，有序的话就不用再接着比较了 for(j=0;j<n-1-i;j++){int temp=0;if(a[j]>a[j+1])//要求递增 {temp=a[j+1];a[j+1]=a[j];a[j]=temp;flag=0;}}if(flag==1)//如果没有交换，则不要调整了，直接退出循环即可。 break;}}
void  PrintSort(int *a,int n)
{int i;for(i=0;i<n;i++){printf("%d ",a[i]);}printf("\n");
}
int main()
{int a[6]={5,6,8,9,1,2};BubbleSort(a,6);PrintSort(a,6);return 0;} 

二、快速排序

1.1简介：

        快速排序类似于前序遍历二叉树，每次选第一个元素作为基准元素，每进行一次快排，找到其基准元素位置后，从该位置左右划分成两部分，左边比基准小，右边比基准大。随后进入左边进行快排，左边都结束了，再去右边。是个递归操作。

        快排的时候，选一个基准元素，定左右两个low和high标记量，low标记的位置都应该比基准小于等于，high标记的都应该大于等于。先是标记处非空数据（逻辑上给开始基准元素处变为空。存到一个pivot基准变量中）的位置进行移动判断，往中间移动。如果high处大于等于基准，则--hgh，如果不满足，则给该处值赋值给low处，即a[low]=a[high]。这样high处变为空了，开始从low处判断.

        时间复杂度：O()

        空间复杂度：树的深度

        稳定性：不稳定，一次移动好多数据

        递归深度：树的高度

        递归次数：树的总结点数

        n个数据，快速排序至少比较多少次？正好平分，次数最少。

        如15个数据，第一次有一个基准元素，分成左右两块长度为7的，此时比较2*7=14，；两个7随后又分成两个长度为3的，四个3最后分成左右长度为1的。因此为2*7+2*2*3+4*2=14+12+8=34

1.2代码：

#include <stdio.h>
void  PrintSort(int *a,int n)
{int i;for(i=0;i<n;i++){printf("%d ",a[i]);}printf("\n");
}
//快速排序
//一次快排
int  Partition(int *a,int low,int high)
{int pivot =a[low];//定义基准元素变量 while(low<high)//进入比较 {while(low<high&&a[high]>=pivot) --high; //最开始标记处为非空开始移动，因此先判断右边high情况，应该high标记处比基准大于等于，满足，往中间移动--。 a[low]=a[high];//不满足high标记处大于等于基准元素，则给该high处值赋值给low标记处while(low<high&&a[low]<=pivot) ++low;a[high]=a[low];//不满足low标记处小于等于基准元素，则给该low处值赋值给high标记处}a[low]=pivot;//当low和high相等时，找到基准元素位置，给该处赋值 return low; //返回基准元素下标 
}
void QuickSort(int *a,int low,int high) 
{ //类似于前序遍历，一个二叉树。 if(low<high)//递归跳出条件 {int pivot =Partition(a,low,high);//根 QuickSort(a,low,pivot-1);   //左 QuickSort(a,pivot+1,high);  //右 }}int main()
{int a[6]={5,6,8,9,1,2};//BubbleSort(a,6);QuickSort(a,0,5); PrintSort(a,6);return 0;}