package com.sort.demo1;

import java.util.Arrays;

/**
 * 冒泡排序
 */
public class BubbleSort {

    public static void main(String[] args) {
        int[] arr = new int[]{1,4,5,7,3,9,8,0,2,6};
        System.out.println(Arrays.toString(arr));
        bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 冒泡排序算法
     * 第一个for循环：控制共比较多少轮
     * 第二个for循环：控制每次循环中比较的次数
     * @param arr
     */
    public static void bubbleSort(int[] arr){
        for(int i=0;i<arr.length-1;i++){
            for(int j=0;j<arr.length-1-i;j++){
                if(arr[j]>arr[j+1]){
                    int temp = arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                }
            }
        }
    }
}

package com.sort.demo1;

import java.util.Arrays;

/**
 * 快速排序
 */
public class QuickSort {
    
    public static void main(String[] args) {
        int[] arr = new int[]{1,4,5,7,3,9,8,0,2,6};
        System.out.println(Arrays.toString(arr));
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 快速排序算法
     * @param arr
     * @param start
     * @param end
     */
    public static void quickSort(int[] arr,int start,int end){
        if(start<end){
            //把数组中的第start个数字作为标准数
            int stard = arr[start];
            //记录需要排序的下标
            int low = start;
            int high = end;
            //循环找到比标准数大的数 和 比标准数小的数
            while (low<high){
                //如果右边的数字比标准数大，右边的下标-1
                while (low<high && stard<=arr[high]){
                    high--;
                }
                //使用右边的数字替换左边的数字
                arr[low] = arr[high];
                //如果左边的数字比标准数小，左边的下标+1
                while (low<high && stard>arr[low]){
                    low++;
                }
                arr[high] = arr[low];
            }
            //把标准数赋值给low低所在的位置的元素(这个时候low=high)
            arr[low] = stard;
            //处理所有的小的数字
            quickSort(arr,start,low);
            //处理所有的大的数字
            quickSort(arr,low+1,end);
        }
    }
}

目录

• 前言
• 1.交换排序——冒泡排序
• 1.1 算法思想
• 1.2 动图演示
• 1.3 冒泡最好的情况
•  2. 交换排序——快速排序
• 2.1 快速排序——挖坑法
• 快排的缺点
• 三数取中法
• 2.3 快速排序——左右指针法
• 2.4 前后指针法

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define N 10
 
Swap(int *p1, int * p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void Print(int *a)
{
	for (int i=0;i<N;i++)
	{
		printf("%d ",a[i]);
	}
}
void BubbleSort(int* a, int n)
{
	
	for (int j=0;j<n;++j)
	{
		int size = 0;
		for (int i=1;i<N-j;++i)
		{
			if (a[i-1]>a[i])
			{
				Swap(&a[i-1],&a[i]);
				size =1;
			}
		}
		if (size==0)
		{
			break;
		}
	}
}
int main()
{
	int a[N] = {0};
	for (int i=0;i<N;++i)
	{
		a[i] = rand();
	}
	BubbleSort(a,N);
	Print(a);
	
	return 0;
}

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
//打印
void Print(int *a,int n)
{
	for (int i=0;i<n;++i)
	{
		printf("%d ",a[i]);
	}
}
//挖坑法
void QuickSort(int* a,int left,int right)//升序
{
	if (left < right)
	{
		int begin = left;
		int end = right;
		int pivot = begin;//记录坑位的下标
		int key = a[begin];//坑值
 
		while (begin < end)
		{
			//右边找小，放到左边
			while (begin < end && a[end] >= key)//与坑值比较
			{
				--end;
			}
			//小的放在左边的坑里，自己形成了新的坑位
			a[pivot] = a[end];
			pivot = end;
 
			//左边找大，放在右边
			while (begin < end && a[begin] <= key)//与坑值比较
			{
				++begin;
			}
			//大的放在右边的坑里，自己形成了新的坑位
			a[pivot] = a[begin];
			pivot = begin;
		}
		//最后将坑值给到坑位
		a[pivot] = key;
		//[left,right]
		//[left,pivot-1]  [pivot+1,right]
		//左子区间和右子区间有序，我们就有序了，如何让他们有序？分治递归
		QuickSort(a, left, pivot - 1);
		QuickSort(a, pivot + 1, right);
	}
	else
	{
		return;
	}
}
int main()
{
	int a[10] = {0,9,5,6,3,2,1,7,8,4};
	//挖坑法
	QuickSort(a,0,sizeof(a)/sizeof(a[0])-1);
    //打印
	Print(a,sizeof(a) / sizeof(a[0]));
	return 0;
}

int begin = left;
int end = right;
//使用三数取中选“坑值”，用mid存储其下标
int mid = GetMidIndex(a, begin, end);
//将区间首值当作坑位
//坑值与首值交换，避免算法混乱
//一般我们会将区间首值作为坑值
Swap(&a[begin], &a[mid]);//传地址调用
//存储坑值
int key = a[begin];

int GetMidIndex(int *a,int left,int right)
{
    //二分
	int mid = (right - left) / 2;
	if (a[left]<a[mid])
	{
		if (a[left]<a[right])
		{
			if (a[mid]<a[right])
			{
				return mid;
			}
			else  //a[mid]>=a[right]
			{
				return right;
			}
		}
		else   //a[left]>=a[right]
		{
			return left;
		}
	}
	else  //a[left]>=a[mid]
	{
		if (a[mid]<a[right])
		{
			if (a[left]<a[right])
			{
				return left;
			}
			else  //a[left]>=a[right]
			{
				return right;
			}
		}
		else  //a[mid]>=a[right]
		{
			return mid;
		}
	}
}

//交换
void Swap(int* p1, int*p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

//区间[left,right]
//左区间[left,pivot-1]  右区间[pivot+1,right]
//左子区间和右子区间有序，我们就有序了，如何让他们有序？分治递归
// 小区间优化
if (pivot - 1 - left > 10)//对当待处理数据大于于10的子序列进行快排递归排序
{
	//快排
	QuickSort(a,left,pivot-1);
}
else
{
	//采用直接插入排序，对当待处理数据低于10的子序列进行排序，避免递归
	InsertSort(a+left,pivot-1-left+1);//为什么最后要加1,例如：区间[0,9]实际上有10个数
}
 
if (right - (pivot + 1) > 10)
{
	QuickSort(a,pivot+1,right);
}
else
{
	InsertSort(a + pivot+1, right-(pivot+1)+1);
 
}

void QuickSort(int* a, int left, int right)
{
	if (left < right)
	{
		int begin = left;
		int end = right;
		//选坑位
		int mid = GetMidIndex(a, begin, end);//三数取中
		Swap(&a[begin], &a[mid]);
		int key = begin;
		while (begin < end)
		{
			while (begin < end && a[end] <= a[key])
				--end;
			while (begin < end && a[begin] >= a[key])
				++begin;
			Swap(&a[begin], &a[end]);
		}
		Swap(&a[begin], &a[key]);
		//分治递归
		QuickSort(a, left, begin - 1);
		QuickSort(a, begin + 1, right);
	}
}

//左右指针法
void QuickSort(int* a, int left, int right)
{
	if (left < right)
	{
		//选坑位
		int mid = GetMidIndex(a, left,right);//三数取中
		Swap(&a[left], &a[mid]);
		int key = left;
		//初始化指向
		int prev = left, cur = left + 1;
		while (cur<=right)
		{
			if (a[cur] <= a[key])//&&++prev!=cur
			{
				++prev;
				//避免无效操作
				if(cur!=prev)
				Swap(&a[prev],&a[cur]);
			}
			++cur;
		}
		Swap(&a[key], &a[prev]);
		//分治递归
		QuickSort(a, left, prev - 1);
		QuickSort(a, prev + 1, right);
	}
}

• C语言中的冒泡排序问题
• C语言中qsort函数用法及用冒泡排序实现
• C语言深入探究冒泡排序与堆排序使用案例讲解
• C语言详解冒泡排序实现
• C语言实现冒泡排序算法的示例详解
• c语言冒泡排序和选择排序的使用代码
• C语言冒泡排序算法代码详解
• C语言冒泡排序超全面实现流程