sort.cpp

常见算法的代码包

//========================冒泡==========================

void bubbleSort(int *list, int n)
{
	int i = 0, j = 0;
	int temp = 0;
	int flag = 1;
	for(i = 1; i <= n-1; i ++)
	{
		flag = 1;
		for(j = n-1; j >= i; j--)
		{
			if(*(list + j) < *(list + j -1))
			{
				temp = list[j];
				list[j] = list[j - 1];
				list[j - 1] = temp;
				flag = 0;
			}
		}
		if(flag == 1)
			return;
	}
}

//========================选择==========================

void selectSort(int *list, int n)
{
	int i, j, min, temp;
	for(i = 0; i < n - 1; i++)
	{
		temp = list[i];
		min = i;
		for(j = i + 1; j < n; j++)
		{
			if(list[j] < list[min])
				min = j;
		}
		if(i != j)
		{
			list[i] = list[min];
			list[min] = temp;
		}
	}
}

//========================插入==========================

void InsertSort(int data[], int n)
{
    for (int i = 1; i < n; ++i)
    {        
        int insertPos = i; 
        int insertValue = data[i];     
        while( insertPos >= 1 && insertValue < data[insertPos-1])
        {
            data[insertPos] = data[insertPos-1];
            --insertPos;            
        } 
        data[insertPos] = insertValue;
    }
}

//========================二分插入==========================

void binaryInsertSort(int *list, int n)
{
	int temp = 0;
	int low = 0, high = 0,mid = 0;
	for(int i = 1; i < n ; i++)
	{
		temp = list[i];
		low = 0;
		high = i - 1;
		while(low <= high)
		{
			mid = (low + high)/2;
			if(temp > list[mid])
			{
				low = mid + 1;
			}
			else
			{
				high = mid - 1;
			}
		}
		for(int j = i; j > low; j--)
		{
			list[j] = list[j-1];
		}
		list[low] = temp;
	}
}

//========================希尔==========================

void ShellSort(int data[], int n)
{ 
    int delta = n; 
    while( delta > 1)
    {
        delta = (delta + 1)/2; // 改变增量
        for (int i = delta; i < n; i++)
        {
            int insertPos = i; 
            int insertValue = data[i]; 
            while (insertPos >= delta && insertValue < data[insertPos-delta])
            { 
                data[insertPos] = data[insertPos-delta]; // 后移数据 
                insertPos -= delta; 
            }
            data[insertPos] = insertValue; // 插入到正确的位置
        }
    }
}

//========================快排==========================

int partition(int *list, int low, int high)
{
	int pivotKey = list[low];
	while(low < high)
	{
		while(low < high && list[high] >= pivotKey)
			high--;
		list[low] = list[high];
		while(low < high && list[low] <= pivotKey)
			low++;
		list[high] = list[low];
	}
	list[low] = pivotKey;
	return low;
}

void qSort(int *list, int low, int high)
{
	int pivot;
	if(low < high)
	{
		pivot = partition(list, low, high);
		qSort(list, low, pivot - 1);
		qSort(list, pivot + 1, high);
	}
}

void quickSort(int *list, int n)
{
	qSort(list, 0, n - 1);
}

//========================归并==========================

void merge(int *list, int *temp, int start, int mid, int end)
{
	int i, j, k;
	for(i = start, k = start, j = mid + 1; i <= mid && j <= end; k++)
	{
		if(list[i] < list[j])
			temp[k] = list[i++];
		else
			temp[k] = list[j++];
	}
	if(i <= mid)
	{
		while(k <= end)
			temp[k++] = list[i++];
	}
	else if(j <= end)
	{
		while(k <= end)
			temp[k++] = list[j++];
	}
	for(i = start; i <= end; i++)
	{
		list[i] = temp[i];
	}
}

void MSort(int *list, int *temp, int start, int end)
{
	int mid;
    if(start < end)
	{
		mid = (start + end)/2;
		MSort(list, temp, start, mid);
		MSort(list, temp, mid + 1, end);
		merge(list, temp, start, mid, end);
	}
}

void mergeSort(int *list, int n)
{
	int *temp = (int *)malloc(sizeof(int) * n);
	if(!temp)
		exit(1);
	MSort(list, temp, 0, n - 1);
	free(temp);                       //!!!
}

//========================堆排==========================

void heapAdjust(int *list, int start, int end)
{
	int temp;
	int i = 2*start + 1;
	while(i <= end)
	{
		if(i < end && list[i + 1] > list[i])
			i++;
		if(list[start] < list[i])
		{
			temp = list[start];
			list[start] = list[i];
			list[i] = temp;
			start = i;
			i = 2*i + 1;
		}
		else
			break;
	}
}

void heapSort(int *list, int n)
{
	int i;
	int temp;
	for(i = (n - 2)/2; i >= 0; i--)
	{
		heapAdjust(list, i, n - 1);
	}
	for(i = 0; i < n - 1; i++)
	{
		temp = list[0];         //!!!!!!!!!!!!!!!!!!!!!!!!!!!
		list[0] = list[n - i - 1];
		list[n - i - 1] = temp;
		heapAdjust(list, 0, n - i - 2);
	}
}