算法分析
一个排序算法的好坏，一般是通过下面几个关键信息来分析的，下面先介绍一下这几个关键信息，然后再将常见的排序算法的这些关键信息统计出来。
名词介绍
- 时间复杂度：指对数据操作的次数（或是简单的理解为某段代码的执行次数）。举例：O(1)：常数时间复杂度；O(log n)：对数时间复杂度；O(n)：线性时间复杂度。
- 空间复杂度：某段代码每次执行时需要开辟的内存大小。
- 内部排序：不依赖外部的空间，直接在数据内部进行排序；
- 外部排序：数据的排序，不能通过内部空间来完成，需要依赖外部空间。
- 稳定排序：若两个元素相等：a=b，排序前a排在b前面，排序后a仍然在b后面，称为稳定排序。
- 不稳定排序：若两个元素相等：a=b，排序前a排在b前面，排序后a有可能出现在b后面，称为不稳定排序。
常见的排序算法的这几个关键信息如下：
冒泡排序
冒泡排序是一种简单直观的排序算法，它需要多次遍历数据；
主要有这么几步：
- 将相邻的两个元素进行比较，如果前一个元素比后一个元素大那么就交换两个元素的位置，经过这样一次遍历后，最后一个元素就是最大的元素了；
- 然后再将除最后一个元素的剩下的元素，重复执行上面相邻两元素比较的步骤。
- 每次对越来越少的元素重复上面的步骤，直到就剩一个数字需要比较。
这样最终达到整体数据的一个有序性了。
动图演示
冒泡排序：
/**
* 冒泡排序
* @param array
*/
public static void bubbleSort(int[] array){
if(array.length == 0){
return;
}
for(int i=0;i<array.length;i++){
// 每一次都减少i个元素
for(int j=0;j<array.length-1-i;j++){
// 若相邻的两个元素比较后，前一个元素大于后一个元素，则交换位置。
if(array[j]>array[j+1]){
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}
当数组中的元素已经是正序时，执行效率最高。
当数组中的元素是一个倒序时，执行效率最低，相邻的元素每次比较都需要交换位置。
而且冒泡排序是完全在数据内部进行的，不需要额外的空间，所以空间复杂度是O(1)。
选择排序
选择排序是一种简单粗暴的排序方式，每次都从数据中选出最大或最小的元素，最终选完了，那么选出来的数据就是排好序的了。
主要步骤：
- 先从全部数据中选出最小的元素，放到第一个元素的位置（选出最小元素和第一位位置交换位置）；
- 然后再从除了第一个元素的剩余元素中再选出最小的元素，然后放到数组的第二个位置上。
- 循环重复上面的步骤，最终选出来的数据都放前面了，数据就排好序了。
动图演示
public static void selectSort(int[] array){
for(int i=0;i<array.length;i++){
// 先以i为最小值的下标
int min = i;
// 然后从后面的数据中找出比array[min] 还小的值，就替换min为当前下标。
for(int j=i+1;j<array.length;j++){
if(array[j]<array[min]){
min = j;
}
}
// 最终如果最小值的下标不等于i了，那么将最小值与i位置的数据替换，即将最小值放到数组前面来，然后循环整个操作。
if(min != i){
int t<em style="color:transparent">本文来源[email protected]搞@^&代*@码)网9</em>emp = array[i];
array[i] = array[min];
array[min] = temp;
}
}
}
搞代码网（gaodaima.com）提供的所有资源部分来自互联网，如果有侵犯您的版权或其他权益，请说明详细缘由并提供版权或权益证明然后发送到邮箱[email protected]，我们会在看到邮件的第一时间内为您处理，或直接联系QQ：872152909。本网站采用BY-NC-SA协议进行授权
转载请注明原文链接：Java多种经典排序算法(含动态图)
转载请注明原文链接：Java多种经典排序算法(含动态图)
