1、冒泡排序
实现过程：假设有10个数，第一轮循环，第一个数和第二个数比较，如果第一个数大，第一个数和第二个数交换位置，否则不动；接着第二个数和第三个数比较，如果第二个数大，第二个数和第三个数交换位置， 否则不动……第九个数和第十个数比较，如果第九个数大，第九个数和第十个数交换位置，否则不动。第一轮循环结束，最大的数挪到了第十个数的位置，比较进行了9次。 第二轮循环，第一个数和第二个数比较，如果第一个数大，第一个数和第二个数交换位置，否则不动……第八个数和第九个数比较，如果第八个数大，第八个数和第九个数交换位置，否则不动。第二轮循环结束 ，第二大的数挪到了第九个数的位置，比较进行了8次。 …… 第九轮循环，第一个数和第二个数比较，如果第一个数大，第一个数和第二个数交换位置，否则不动。第九轮循环结束，倒数第二大的数挪到了第二个数的位置，比较进行了1次。 总体原理：每轮比较找到最大的数。 个人理解：分两次循环，外循环和内循环；外循环是n个数需要进行几次循环，内循环是每次外循环需要两两比较的次数； 每次外循环将最大或最小的数移至最右端，第二次循环时不再需要考虑最后一个数； 算法:外循环次数是：====n-1次 内循环的次数是：====n-i-1
时间复杂度：O(n2)
稳定性分析：冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，是不会再交换的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。
实现：
public int[] bubble(int[] arr) {
int tmp=0;
for(int i = 0;i<arr.length-1;i++) {
for(int j=0;j<arr.length-1-i;j++) {
if(arr[j+1]<arr[j]) {
tmp=arr[j+1];
arr[j+1]=arr[j];
arr[j]=tmp;
}
}
}
return arr;
}
2、选择排序
实现过程：在数组的前提下，每次外循环遍历最小带的值（或最大的值）存到前面，后一次循环，从存好的最大（或最小的值）后一位开始遍历再找到 最大（或最小值）存到前面；n个数，外循环需要n-1次； 个人理解：定义一个中间变量，min存放最小值，且初始值都默认是开始遍历的第一位，用index记录最小值的下标，每次内循环找到最小值存到min,下标存到index，然后和开始遍历的第一个元素更换；
时间复杂度：O(n2)
稳定性分析：选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中两个5的相对前后顺序就被破坏了，所以选择排序是一个不稳定的排序算法。
public int[] option(int arr[]) {
int xiabiao=0;
int tmp=0;
for(int i=0;i<arr.length-1;i++) {
int max = arr[i];
for(int j=1+i;j<arr.length;j++) {
if(arr[j]>max) {
max = arr[j];
xiabiao = j;
}
}
if(arr[i]!=max) {
tmp=arr[xiabiao];
arr[xiabiao]=arr[i];
arr[i]=tmp;
}
}
return arr;
}
3、插入排序
实现过程：在数组的前提下，也分为外循环和内循环，从第二个数开始比较，与前面的每一个数比，如果小于 前面的数，则插入到前面的数前面，否则退出循环 个人理解：从第二个数开始比较，与前面的数比，大于则退出循环，小于则插入前面的数前面，以此类推
时间复杂度：O(n2)
稳定性分析：如果待排序的序列中存在两个或两个以上具有相同关键词的数据，排序后这些数据的相对次序保持不变，即它们的位置保持不变，通俗地讲，就是两个相同的数的相对顺序不会发生改变，则该算法是稳定的；如果排序后，数据的相对次序发生了变化，则该算法是不稳定的。关键词相同的数据元素将保持原有位置不变，所以该算法是稳定的
public int[] insert(int arr[]) {
int tmp =0;
for(int i =1;i<arr.length;i++) {
for(int j=i-1;j>=0;j--) {
if(arr [i]>arr[j]) {
tmp= arr[i];
arr[i]=arr[j];
arr[j]=tmp;
i--;
}
}
}
return arr;
}
4、希尔排序
实现过程：它分为三个循环，最外层是控制增量的，后两个其实就是插入排序，i代表第二层for循环，j代表第三层for循环，i的话是数组下标每次向右增加一个增量（也就是小组成员加一了，这时，这个 新增的成员要分别与本小组的其他成员比较，这就用到了变量j），增量公式：n/2 个人理解：它是插入排序的变种（优化），插入排序是将前面部分看成一个整体数组，后面遍历的数分别与这个数组的每个值比较，而希尔排序是将数据按照增量分为了几个小组，每个小组内部实现 插入排序，
时间复杂度：O(n^(1.3)) -O(n^(2)) 之间，反正是小于O(n2)
稳定性分析：由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。
public static void shell(int arr[]) {
int tmp = 0;
for(int gap=arr.length/2;gap>0;gap/=2){
for(int i=gap;i<arr.length;i++){
int j = i;
while(j-gap>=0 && arr[j]<arr[j-gap]){
tmp = arr[j];
arr[j]=arr[j-gap];
arr[j-gap]=tmp;
j-=gap;
}
}
}
}
5、快速排序
链接：https://blog.csdn.net/nrsc272420199/article/details/82587933
快速排序,说白了就是给基准数据找其正确索引位置的过程.
设数组为： 23、46、0、8、11、18
假设最开始的基准数据为数组第一个元素23,则首先用一个临时变量去存储基准数据,即tmp=23;然后分别从数组的两端扫描数组，设两个指示标志:low指向起始位置，high指向末尾. 用一个临时变量存储基准数据23 tmp=23；
首先从后半部分开始，如果扫描到的值大于基准数据就让high减1,如果发现有元素比该基准数据的值小(如上图中18<=tmp)，就将high位置的值赋值给low位置
结果为：18、46、0、8、11、18
然后开始从前往后扫描,如果扫描到的值小于基准数据就让low加1,如果发现有元素大于基准数据的值(如上图46=>tmp)，就再将low位置的值赋值给high位置的值,
结果为：18、46、0、8、11、46
最终23的位置为：4
也就是：18、11、0、8、23、46
后续操作采用递归
时间复杂度：O(nlogn)
稳定性分析：不稳定。基准数字的换位时发生
package sort;
public class quickSort {
public static void quick(int [] arr,int low,int high) {
if(low<high) {
int index=getIndex(arr,low,high);
quick(arr,low,index-1);
quick(arr,index+1,high);
}
}
public static int getIndex(int[] arr,int low,int high) {
int tmp = arr[low];
while(low<high) {
while(low<high&&arr[high]>=tmp) {
high--;
}
arr[low]=arr[high];
while(low<high&&arr[low]<=tmp) {
low++;
}
arr[high]=arr[low];
}
arr[low]=tmp;
return low;
}
public static void main(String[] args) {
int[] arr = { 23,46,0,8,11,18 };
quick(arr, 0, arr.length - 1);
System.out.println("排序后:");
for (int i : arr) {
System.out.println(i);
}
}
}
6、归并排序
链接：https://www.cnblogs.com/chengxiao/p/6194356.html
实现过程：给定一个无序数组，然后写一个递归方法和一个合并方法，递归负责将无序数组分解为单个的数字，在回溯阶段，调用合并方法 个人理解：利用了分治思想，分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之 一堆数据，一直拆分，直至分为一个一个的数，然后将单个数字合并为两个数字（有序的），再两两合并为四个数字（有序的），一直这样下去，直到又组合成 一行数，至此，排序完成。 合并是利用一个临时数组，两个指针，这两个指针开始默认指向两个即将合并的数组的第一位，分别比较，最后合并到临时数组中去 在代码实现中，可以用递归回溯的方式，先拆后合。
时间复杂度：O(nlogn)
稳定性分析：因为交换元素时，可以在相等的情况下做出不移动的限制，所以归并排序是可以稳定的
public class mergeSort {
public static void sort(int []arr) {
int temp[] = new int[arr.length];
sort(arr,0,arr.length-1,temp);
}
public static void sort(int[] arr,int left,int right,int [] temp) {
if(left<right) {
int mid =(left+right)/2;
sort(arr,left,mid,temp);
sort(arr,mid+1,right,temp);
merge(arr,left,mid,right,temp);
}
}
public static void merge(int[]arr,int left,int mid,int right,int[]temp) {
int i=left;
int j=mid+1;
int t=0;
while(i<=mid&&j<=right) {
if(arr[i]<=arr[j]) temp[t++]=arr[i++];
else temp[t++]=arr[j++];
}
while(i<=mid) temp[t++]=arr[i++];
while(j<=right) temp[t++]=arr[j++];
t=0;
while(left<=right) arr[left++]=temp[t++];
}
public static void main(String[] args) {
int []arr = {9,8,7,6,5,4,3,2,1};
sort(arr);
System.out.println(Arrays.toString(arr));
}
}
7、堆排序
堆的概念：
每个结点的值都大于或等于其左右孩子结点的值的完全二叉树，称为大顶堆；
每个结点的值都小于或等于其左右孩子结点的值的完全二叉树，称为小顶堆；
堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序
可以用数组来表示堆：
大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
思路：
利用堆进行排序，将待排的序列构成个大顶堆，最大值就是根节点；将根节点移走，（将其和堆末尾元素交换，此时末尾 元素就是最大值），接着将剩余的n-1个序列重新构成一个堆，继续进行。
个人理解：第一步：创建一个大顶或小顶堆 第二步：依次将堆顶元素和尾元素交换，然后重新将剩余的元素构建堆
时间复杂度：它的最坏，最好，平均时间复杂度均为O(nlogn)
稳定性分析：不稳定
public class heapSort {
public static void main(String []args){
int []arr = {9,8,7,6,5,4,3,2,1};
sort(arr);
System.out.println(Arrays.toString(arr));
}
public static void sort(int []arr){
for(int i=arr.length/2-1;i>=0;i--){
adjustHeap(arr,i,arr.length);
}
for(int j=arr.length-1;j>0;j--){
swap(arr,0,j);
adjustHeap(arr,0,j);
}
}
public static void adjustHeap(int []arr,int i,int length){
int temp = arr[i];
for(int k=i*2+1;k<length;k=k*2+1){
if(k+1<length && arr[k]<arr[k+1]){
k++;
}
if(arr[k] >temp){
arr[i] = arr[k];
i = k;
}else{
break;
}
}
arr[i] = temp;
}
public static void swap(int []arr,int a ,int b){
int temp=arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
}
|