今天总结一下经常遇到的四种算法
第一种：冒泡排序
/*
* 排序思想：
1. 比较相邻的元素。如果第一个比第二个大（升序），就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步 做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要 比较为止。
*/
public class MaoPaoSort {
public static void swap(int[] arr,int i,int j)
{
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
public static int[] msort(int[] arr)
{
for(int i=0;i<arr.length;i++)
{
for(int j=0;j<arr.length-i-1;j++)
{
if(arr[j]>arr[j+1])
{
swap(arr,j,j+1);
}
}
}
return arr;
}
public static void main(String[] args) {
int[] arr = new int[] {44,62,-23,47,39,90,-11,12,63,59};
for(int i=0;i<10;i++)
{
System.out.println(msort(arr)[i]);
}
}
}
第二种：选择排序
/*
* 选择排序是一种简单直观的排序算法，工作原理为：在未排序的序列中找出最小(大)元素与第一个位置的元素交换位置
注意选择排序与冒泡排序的区别：冒泡排序通过依次交换相邻两个顺序不合法的元素位置，从而将当前最小（大）元素放到合适的位置；而选择排序每遍历一次都记住了当前最小（大）元素的位置，最后仅需一次交换操作即可将其放到合适的位置。
然后在剩下的元素中再找最小(大)元素与第二个元素的位置交换，依此类推，直到所有元素排序排序完成。根据上述描述，一共进行n-1趟比较后，就能完成整个排队过程。我们可以知道，第k趟比较需要进行的数组元素的两两比较的次数为n-k次，所以共需要的比较次数为n*(n-1) / 2，因此选择排序算法的时间复杂度与冒泡排序一样，也为O(n^2)。
算法简介：
1.初始状态：序列为无序状态。
2.第1次排序：从n个元素中找出最小(大)元素与第1个记录交换
3.第2次排序：从n-1个元素中找出最小(大)元素与第2个记录交换
4.第i次排序：从n-i+1个元素中找出最小(大)元素与第i个记录交换
5.以此类推直到排序完成
*/
public class SelectSort {
public static void sort(int[] arr)
{
for(int i=0;i<arr.length;i++)
{
int min=i;
for(int j=i;j<arr.length;j++)
{
if(arr[min]>arr[j])
{
min=j;
}
}
int temp=arr[i];
arr[i]=arr[min];
arr[min]=temp;
}
}
public static void main(String[] args) {
int[] arr = new int[] {44,62,-23,47,39,90,-11,12,63,59};
sort(arr);
for(int i=0;i<10;i++)
{
System.out.println(arr[i]);
}
}
}
第三种：插入排序
/*
* 对于n个元素，一共需要进行n-1轮比较，
* 而第k轮比较需要进行k次数组元素的两两比较，
* 因此共需要进行的比较次数为：1 + 2 + ... + (n-1)
* 所以插入排序的时间复杂度同冒泡排序一样，也为O(n^2)。
* 算法简介：
1.从第一个元素开始，该元素可认为已排序。
2.取出下一个元素，在排序好的元素序列中从后往前扫描
3.如果元素(已排序)大于新元素，将该元素移到下一位置
4.重复3.直到找到已排序的元素小于或等于新元素的位置
5.将新元素插入该位置后
6.重复2-5直到排序完成
*/
public class InsertSort {
public static void sort(int[] arr)
{
for(int i=0;i<arr.length-1;i++)
{
for(int j=i+1;j>0;j--)
{
if(arr[j]<arr[j-1])
{
int temp=arr[j];
arr[j]=arr[j-1];
arr[j-1]=temp;
}
else {
break;
}
}
}
}
public static void main(String[] args) {
int[] arr = new int[] {44,62,-23,47,39,90,-11,12,63,59};
sort(arr);
for(int i=0;i<10;i++)
{
System.out.println(arr[i]);
}
}
}
第四种：快速排序（最经典）
/*
* 介绍： 快速排序通常明显比同为O(nlogn)的其他算法更快，因此常被采用，而且快 排采用了分治法的思想，所以在很多笔试面试中能经常看到快排的影子。可 见掌握快排的重要性。
快速排序（Quick Sort）由图灵奖获得者Tony Hoare发明，被列为20世纪十 大算法之一，是迄今为止所有内排序算法中速度最快的一种。冒泡排序的升 级版，交换排序的一种。快复速排序的时间杂度为O(nlog(n))。
排序思想：
1. 从数列中挑出一个元素，称为"基准"（pivot），
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，
所有元素比基准 值大的摆在基准的后面（相同的数可以到任一边）。
在这个分区结束之后， 该基准就处于数列的中间位置。这个称为分区（partition）操作。
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数 列排序。
4. 递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好 了。
虽然一直递归下去，但是这个算法总会结束，因为在每次的迭代 （iteration）中，
它至少会把一个元素摆到它最后的位置去。
*/
public class QuickSort {
public static void swap(int[] arr,int i,int j) //交换
{
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
public static void sort(int[] arr,int left,int right)
{
if(left>right)
{
return;
}
int base=arr[left];
int l=left;
int r=right;
while(l != r)
{
while(arr[r]>=base && l<r)
{
r--;
}
while(arr[l]<=base && l<r)
{
l++;
}
if(l<r)
{
swap(arr,l,r);
}
}
arr[left] = arr[l];
arr[l] = base;
sort(arr,left,l-1);
sort(arr,r+1,right);
}
public static void quickSort(int[] arr)
{
if(arr.length<=1)
{
return;
}
sort(arr,0,arr.length-1);
}
public static void main(String[] args) {
int[] arr = new int[] {44,62,-23,47,39,90,-11,12,63,59};
quickSort(arr);
for(int i=0;i<10;i++)
{
System.out.println(arr[i]);
}
}
}
排序算法性能分析
1.从平均时间而言：快速排序最佳。但在最坏情况下时间性能不如堆排序和归 并排序。
2.从算法简单性看：由于直接选择排序、直接插入排序和冒泡排序的算法比较 简单，将其认为是简单算法。对于Shell排序、堆排序、快速排序和归并排序 算法，其算法比较复杂，认为是复杂排序。
3.从稳定性看：直接插入排序、冒泡排序和归并排序时稳定的；而直接选择排序、快速排序、 Shell排序和堆排序是不稳定排序
4.从待排序的记录数n的大小看，n较小时，宜采用简单排序；而n较大时宜采 用改进排序。
版权声明：本文为z710757293原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。