文章目录阅读这篇文章就证明你已经开始踏上了算法的修仙之路,接下来我会两天一更,介绍图解算法里面的算法的实现, 适合Java程序员阅读。
- 前言
- 一、什么是分治思想?
- 1.核心思想
- 2.案例展示
- 二、快速排序和选择排序的比较
- 三、快速排序实现
- 1.实现步骤
- 2.python实现
- 3.Java实现
- 4.两者比较
- 总结
前言
提示:这里可以添加本文要记录的大概内容:
接着上一篇递归之后,学习快速排序,需要的基础有递归思想,分治思想。
其中递归思想在前两篇中也讲到过该思想,这篇重点了解分治思想。
提示:以下是本篇文章正文内容,下面案例可供参考
分治的核心思想: 就是将一个问题N分解成多个子问题K, 求解子问题的解,就是求最终问题的解。有些简单的问题还可以用二分算法。
百度百科的分治算法介绍地址
2.案例展示二、快速排序和选择排序的比较将一个数组[5,8,3,7,1,4]进行排序,用分治的思想去求解,其实就是把大数组分成很多小数组,将小数组排好序合并,大数组排序的问题就解决了。
三、快速排序实现 1.实现步骤快速排序: 糟糕情况的运行时间为O(n * n), 平均情况为O(n * logn)
比较排序: 比较稳定,运行时间为O(n * n)
相比之下:
快速排序算是排序算法里面比较快的算法之一。
所有我们需要去学习快速排序,包括里面包含的思想。
2.python实现1.找到基准数, 比如刚开始我找的是索引为0元素。
2.将数组分成两个子数组,一个数组大于基准数,另外一个数组小于基准数。
3.对两个子数组进行快速排序
4.每次递归都需要找到基线条件。
def quicksort(array):
if len(array) < 2:
return array
else:
pivot = array[0]
less = [i for i in array[1:] if i <= pivot]
greater = [i for i in array[1:] if i > pivot]
return quicksort(less) + [pivot] + quicksort(greater)
print( quicksort([5,8,3,7,1,4]))
3.Java实现
public class QuickSort {
public static void main(String[] args) {
//数据源
Integer[] myList = new Integer[]{5,8,3,7,1,4};
//快速排序
quickSort(myList,0,myList.length-1);
//打印结果
print(myList);
}
//递归排序
public static void quickSort(Integer[] myList, int low, int high) {
if(low < high){ //基线条件
Integer pivot = partition(myList,low,high); //基准数
quickSort(myList,0,pivot);
quickSort(myList, pivot+1, high); //递归
}
}
//分而治之
public static Integer partition(Integer[] myList, int low, int high) {
Integer pivot = myList[low];
while(low < high){
while(low < high && myList[high] >= pivot){
--high;
}
swap(myList,low,high); //交换法,互换位置
while(low < high && myList[low] <= pivot){
++low;
}
swap(myList,low,high); //交换法,互换位置
}
return low;
}
//交换法
public static void swap(Integer[] myList, int low, int high) {
Integer temp = myList[low];
myList[low] = myList[high];
myList[high] = temp;
}
//打印函数
public static void print(Integer[] myList){
for(int i = 0; i < myList.length; i++){
System.out.print(myList[i] + "->");
}
System.out.println("null");
}
}
4.两者比较
总结python实现快速排序确实更好体现了分治思想,因为有切片和连接的方法。
Java实现快速排序利用的交换法去实现的分区。
思路是一模一样的,但是处理的方式会根据语言的不同而有差异。
下一篇将会介绍广度优先搜索,搜索算法的一种,需要散列表和队列这种数据结构的基础。也希望大家把快速排序掌握,当然分治思想还是入门,需要刷更多的题目去掌握不同场景下的分治的应用。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)