【数据结构】常见的排序算法 -- 交换排序

//1)冒泡排序
void BubbleSort(int* arr, int n)
{
	int exchange = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n - i - 1; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				exchange = 1;
				Swap(&arr[j], &arr[j + 1]);
			}
		}
		if (exchange == 0)
		{
			break;
		}
	}
}

//2)快速排序
void QuickSort(int* arr, int left, int right)
{

	if (left >= right)
	{
		return;
	}
	//找基准值keyi
	int keyi = _QuickSort(arr, left, right);
	//左序列[left,keyi - 1]  右序列[keyi + 1,right]
	QuickSort(arr, left, keyi - 1);
	QuickSort(arr, keyi + 1, right);
}

//找基准值 -- hoare版本
int _QuickSort1(int* arr, int left, int right)
{
	int keyi = left;
	left++;
	while (left <= right)
	{
		//right:从右往左找比基准值要小的
		while (left <= right && arr[right] > arr[keyi])
		{
			--right;
		}
		//left:从左往右找比基准值要大的
		while (left <= right && arr[left] < arr[keyi])
		{
			++left;
		}
		//left和right交换
		if (left <= right)
		{
			Swap(&arr[left], &arr[right]);
			left++;
			right--;
		}
	}
	//right的位置就是基准值的位置
	Swap(&arr[keyi], &arr[right]);//交换值
	return right;
}

int _QuickSort2(int* arr, int left, int right)
{
	int hole = left;
	int key = arr[hole];
	while (left < right)
	{
		while (left < right && arr[right] > key)
		{
			--right;
		}
		arr[hole] = arr[right];
		hole = right;

		while (left < right && arr[left] < key)
		{
			++left;
		}
		arr[hole] = arr[left];
		hole = left;
	}
	arr[hole] = key;
	return hole;
}

//找基准值 -- lomuto前后指针
int _QuickSort3(int* arr, int left, int right)
{
	int prev = left, cur = left + 1;
	int keyi = left;
	while (cur <= right)
	{
		//cur数据和基准值比较
		if (arr[cur] < arr[keyi] && ++prev != cur)
		{
			Swap(&arr[cur], &arr[prev]);
		}
		++cur;
	}
	Swap(&arr[keyi], &arr[prev]);

	return prev;

}

//非递归版本快速排序
// 交换两个元素
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 分区操作：返回基准值最终位置
int partition(int arr[], int left, int right) {
    // 选择最右侧元素作为基准值
    int pivot = arr[right];
    // i 指向小于基准值区域的最后一个元素
    int i = left - 1;
    
    for (int j = left; j < right; j++) {
        // 若当前元素小于等于基准值，加入左侧区域
        if (arr[j] <= pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    // 将基准值放到正确位置（i+1 是基准值的最终索引）
    swap(&arr[i + 1], &arr[right]);
    return i + 1;
}

// 非递归快速排序
void quickSort(int arr[], int n) {
    if (n <= 1) return;
    
    // 用数组模拟栈，存储区间的左右边界（每个区间占两个位置）
    int* stack = (int*)malloc(2 * n * sizeof(int));
    int top = -1;  // 栈顶指针
    
    // 初始区间 [0, n-1] 入栈
    stack[++top] = 0;
    stack[++top] = n - 1;
    
    // 栈不为空时循环处理
    while (top >= 0) {
        // 弹出右边界和左边界（注意栈的先入后出特性）
        int right = stack[top--];
        int left = stack[top--];
        
        // 分区操作，获取基准值位置
        int pivotIndex = partition(arr, left, right);
        
        // 左子区间 [left, pivotIndex-1] 入栈（若有效）
        if (pivotIndex - 1 > left) {
            stack[++top] = left;
            stack[++top] = pivotIndex - 1;
        }
        
        // 右子区间 [pivotIndex+1, right] 入栈（若有效）
        if (pivotIndex + 1 < right) {
            stack[++top] = pivotIndex + 1;
            stack[++top] = right;
        }
    }
    
    free(stack);  // 释放栈内存
}