10大排序,八大排序总结
Yyds干货库存
@TOC
首先，直接插入排序
将待排序的记录按照它们的键值逐一插入到一个有序序列中，直到所有记录都被插入，得到一个新的有序序列。
2.直接插入排序的实现。
Voidinsertport (int * a，int SZ)//直接插入排序[0 end]是有序的，在end 1位置插入的值使得[0 end 1]也是有序的。
int I=0；//假设我们想按升序排序
for(I=0；I SZ-1；I)//不能获取sz-1，否则tmp会造成越界访问。
int end=I；
int tmp=a[end 1]；//最后一个数据
while (end=0)
If (a[end] tmp)//如果数组中的数据大于tmp
a[结束1]=a[结束]；
end-；
其他
打破；//找到比tmp小的东西，结束循环
a[end 1]=tmp；//防止tmp小于所有数据
}
直接插入排序的时间复杂度
第二，希尔排序
其思路是：首先选择一个整数，将待排序文件中的所有记录分组，距离内的所有记录都在同一组，然后对每组中的记录进行排序，重复分组排序，直到=1。
Hill是直接插入排序的优化。
1.首先进行预排序，使数组接近顺序。
2.直接插入排序
这时发现多组的间隔是gap的前序，gap由大变小。
差距越大，大的数字越快来到后面，小的数字越快来到前面。
间隙越大，预排时越不有序。
差距越小，越接近有序。
当gap=1时，直接插入即时排序。
2.希尔排序的实现。
Void shellsort(int* a，int n)//Hill排序
int I=0；
int gap=n；
while(间隙1)
gap=gap/3 1；//同时排列多组有间隙间隔的数据。
for(I=0；I n-gap；I )//如果gap改为1，则直接插入排序。
int end=I；
int tmp=a[端隙]；
while (end=0)
if(一个[end] tmp)
a[末端缺口]=a[末端]；
end=end-gap；
其他
打破；
a[末端间隙]=tmp；
}
3.Hill排序的时间复杂度
Gap=n，gap=gap/3 ^ 1，即n=n/3 ^ 1。
假设x是运算次数3 x=n1x=log3n1
时间复杂度为O(log 3 N)
2.预排序会使数组接近有序。比如gap=1时，是直接插入排序，时间复杂度为O(N)
希尔排序的总时间复杂度为O(N *log 3 N)
第三，直接选择排序。
1.直接选择排序的实现
Voidselectsort (Intarr []，Intn)//直接选择排序
int begin=0；
int end=n-1；
while(开始结束)
int max=begin
int min=begin
int I=0；
for(I=begin；i=结束；我)
if (arr[i] arr[min])
min=I；//通过交换找到最大值的坐标
if (arr[i] arr[max])
max=I；//通过交换找到最小坐标
swap( arr[begin]，arr[min])；//通过坐标将最小值交换到起点
if (begin==max)
max=min
swap( arr[end]，arr[max])；//通过坐标将最大值交换到末尾
开始；
end-；
}
2.有关注意事项
3.直接选择排序的时间复杂度
直接选择排序，不管数组是有序的(最好的情况)还是无序的(最坏的情况)，都需要遍历整个数组，
时间复杂度为o (n 2)
第四，堆排序
点击这里：堆排序的详细解释
第五，冒泡排序
1.冒泡排序的实现。
void bubblesort(int* a，int sz)
int I=0；
int j=0；
for(I=0；I SZ-1；I )//i代表出行次数。我在倒数第二次排列了这个数组。
int exchange=0；
for(j=0；j SZ-1-I；J )//j代表每次行程的对数。
if (a[j] a[j 1])
int tmp=0；
tmp=a[j]；
a[j]=a[j 1]；
a[j 1]=tmp；
交换=1；
If (exchange==0)//表示如果遍历一次后没有比较，就是按顺序。
打破；
}
2.冒泡排序的时间复杂度。
正常情况下：
在第一次行程中，总共比较了n-1次，
在第二次行程中，总共比较了n-2次，
在第n-1次旅行中，总共进行了一次比较。
运算次数为：N-1N-2N-3.1=N (N-1)/2
由大O渐进法省略，时间复杂度为O (n 2)
在最好的情况下：
当数组排序时，例如：1 2 3 4 5
只是按升序，遍历后发现不进入交换，交换==0跳出循环。
时间复杂度为O(N)
3.冒泡排序和直插排序谁更好？
当数组接近顺序时，如：1 2 3 5 4 6
1.气泡排序：
2.直接插入排序：
1 2 3 5 4 6
时间复杂度为O(N)
直接插入排序更好。
。
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。