冒泡与快速排序的算法原理与性能对比
冒泡排序算法原理
从第一个元素开发遍历，比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
void BubbleSort(int* data, int len){int tmp = 0;for(int i = 0; i < len; ++ i){for(int j = 0; j < len - i - 1; ++j){if(data[j+1] < data[j]){tmp = data[j+1];data[j+1] = data[j];data[j] = tmp;}}}}
从代码可以看出这里使用了2层for循环，第一层for循环用于找出数组中第几大的数据，第二次for循环根据上层循环确定的数据和相邻的数据进行比较找出较大者，直到找到未被排序的数据为止。
快速排序算法原理
-
首先设定一个分界值，通过该分界值将数组分成左右两部分。 -
将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。 此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。 -
然后，左边和右边的数据可以独立排序。 对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。 右侧的数组数据也可以做类似处理。 -
重复上述过程，可以看出，这是一个递归定义。 通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。 当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。
void quickSort(int* data, int start, int end){if(start >= end){return;}int low = start;int tmp = data[start];int high = end;tmp = data[start];while(low < high){while(low < high && tmp <= data[high]){--high;}data[low] = data[high];while(low < high && tmp >= data[low]){++ low;}data[high] = data[low];}data[low] = tmp;quickSort(data, start, low -1);quickSort(data, low +1, end);}
-
从算法复杂性上来看，冒泡排序可以从生活中找到场景，实现逻辑相对简单、快速排序由于涉及到每趟都要更新分界值在理解上有一定的复杂度。 -
从算法时间复杂度的角度来看，在对大规模数据进行排序的时候快速排序的优势很明显， 时间消耗相差2000倍 ，这也是STL里面sort函数使用快速排序的原因。 在快速排序里面由于选择分界值方法的不同，这就导致在极端条件下快速排序不够稳定可能会退化为冒泡排序，优先推荐使用三值取中法来选择分界值。相对而言，冒泡排序就非常的稳定。
有任何问题欢迎后台留言，大家一起讨论学习。