C# · 12月 20, 2021

所有常用简单排序算法的c++代码

快速排序:

void QuickSort(int s[],int l,int r)

{

if (l< r)

{

int i = l,j = r,x = s[l];

while (i < j)

{

while(i = x) // 从右向左找第一个小于x的数

j–;

if(i < j)

s[i++] = s[j];

while(i < j && s[i]< x) // 从左向右找第一个大于等于x的数

i++;

if(i < j)

s[j–] = s[i];

}

s[i] = x;

quickSort(s,l,i – 1); // 递归调用

quickSort(s,i + 1,r);

}

}

选择排序:

void SelectSort(int s[],int n)

{

int i,j,k;

for (i=0; i < n-1; i++)

{

k = i;

for (j=i+1; j < n; j++)

{

if (a[j] < a[k]) k = j;

}

if (k != i) swap(s[k],s[i]);

}

}

冒泡排序:

void BubbleSort(int s[],int n)

{

for (int i = 0; i < n; i++)

{

for (int j = 0; j < n – i – 1; j++)

{

if (s[j] > s[j + 1])

{

swap(s[j],s[j + 1]);

}

}

}

}

希尔排序:

void ShellSort(int s[],int n)

{

int gap; //gap为增量,为任意小于n的数

for(gap = 3; gap >0; gap–)

{

for(int i=0; i<gap; i++) //分成gap组

{

for(int j = i+gap; j<n; j=j+gap) //每组进行插入排序(gap=1即为普通插入排序)

{

int temp = s[j],k = j-gap;

while(k>=0&&s[k]>temp)

{

s[k+gap] = s[k];

k = k-gap;

}

s[k+gap] = temp;

}

}

}

}

插入排序:

void InsertSort(int s[],int n)

{

for (int i = 1; i < n; i++) //默认第一个元素已经是有序的,因此从第二个元素开始

{

int j = i-1,temp=s[i];

while (j >=0&&s[j] > temp) //前一个元素比待插元素大

{

s[j+1] = s[j]; //如果待插入元素比拍好元素大,则循环右移大的那部分元素

//留出位置给待插元素

j–;

}

s[j+1] = temp; //插入元素

}

}

归并排序:

/*该函数将数组下标范围[l1,r1]和[l2,r2]的有序序列合并成一个有序序列*/

void merge(int nums[],int l1,int r1,int l2,int r2 ) {

int i = l1; //左半部分起始位置

int j = l2; //右半部分起始位置

int n = (r1 – l1 + 1) + (r2 – l2 + 1); //要合并的元素个数

vector temp(n); //辅助数组

int k = 0; //辅助数组其起始位置

while (i <= r1&&j <= r2) { //挑选两部分中最小的元素放入辅助数组中

if (nums[i] < nums[j])

temp[k++] = nums[i++];

else

temp[k++] = nums[j++];

}

//如果还有剩余,直接放入到辅助数组中

while (i <= r1)

temp[k++] = nums[i++];

while (j <= r2)

temp[k++] = nums[j++];

//更新原始数组元素

for (int i = 0; i < n;i++)

{

nums[l1 + i] = temp[i];

}

}

/*二路归并排序(递归实现)*/

void MergeSort(int nums[],int start,int end) {

if (start < end) {

int mid = (start + end)/2; //分割序列

MergeSort(nums,start,mid); //对序列左半部分进行归并排序

MergeSort(nums,mid + 1,end); //对序列右半部分进行归并排序

merge(nums,mid,end); //合并已经有序的两个序列

}

}

 

堆排序:

void adjust(int arr[],int len,int index)

{

int left = 2 * index + 1;

int right = 2 * index + 2;

int maxIdx = index;

if (left arr[maxIdx]) maxIdx = left;

if (right arr[maxIdx]) maxIdx = right; // maxIdx是3个数中最大数的下标

if (maxIdx != index) // 如果maxIdx的值有更新

{

swap(arr[maxIdx],arr[index]);

adjust(arr,len,maxIdx);// 递归调整其他不满足堆性质的部分

}

}

void heapSort(int arr[],int size)

{

for (int i = size / 2 – 1; i >= 0; i–) // 对每一个非叶结点进行堆调整(从最后一个非叶结点开始)

{

adjust(arr,size,i);

}

for (int i = size – 1; i >= 1; i–)

{

swap(arr[0],arr[i]); // 将当前最大的放置到数组末尾

adjust(arr,i,0); // 将未完成排序的部分继续进行堆排序

}

}