插入排序
void InsertSort(int arr[], int length) //无哨兵的插入排序
{
for(int i=1; i<length; i++)
{
if(arr[i] < arr[i-1])
{
int temp = arr[i];
for(int j=i-1; j>=0 && arr[j]>temp; j--)
{
arr[j+1] = arr[j];
}
arr[j+1] = temp;
}
}
}
void InsertSort(int arr[], int length) //有哨兵的插入排序
{
for(int i=1; i<=length; i++)
{
if(arr[i] < arr[i-1])
{
arr[0] = arr[i];
for(int j=i-1; arj[j]>arr[0]; j--)
{
arr[j+1] = arr[j];
}
arr[j+1] = arr[0];
}
}
}
希尔排序
void shell_sort(int arr[], int length)
{
int d = length / 2;
while(d > 0)
{
for(int i=d; i<length; i++)
{
int temp = arr[i];
int j = i - d;
while(j >=0 && arr[j] > temp)
{
arr[j+d] = arr[j];
j -= d;
}
arr[j+d] = temp;
}
d /= 2;
}
}
选择排序
void SelectSort(int arr[], int length) //简单选择排序
{
for(int i=0; i<length-1; i++)
{
k = i;
for(int j=i+1; j<length; j++) //从后面选择一个最小的记录
{
if(arr[j] < arr[k])
k = j;
}
if(k != i) //与第i个记录交换
swap(arr[i], arr[k]);
}
}
冒泡排序
void Bubble_Sort1(int arr[], int length) //将小元素冒泡到最前面,首先操作小元素
{
for(int i=0; i<length-1; i++)
{
for(int j=i+1; j<length; j++)
{
if(arr[j] < arr[i])
swap(arr[i], arr[j]);
}
}
}
void Bubble_Sort2(int arr[], int length)
{
for(int i=0; i<length; i++)
{
for(int j=0; j<legnth-1-i; j++)
{
if(arr[j] > arr[j+1])
swap(arr[j], arr[j+1]);
}
}
}
void Bubble_Sort3(int arr[], int length)
{
int left = 0;
int right = length - 1;
while(left < right)
{
for(int i=left; i<right; i++)
if(arr[i] > arr[i+1])
swap(arr[i], arr[i+1]);
--right;
for(int j=right; j>left; j--)
if(arr[j] < arr[j-1])
swap(arr[j], arr[j-1]);
++left;
}
}
快速排序
int partition(int* arr, int low, int high)
{
int pivo = arr[low];
while(low < high)
{
while(low < high && arr[high] >= pivo)
high--;
arr[low] = arr[high];
while(low < high && arr[low] <= pivo)
low++;
arr[high] = arr[low];
}
arr[low] = pivo;
return low;
}
void qsort(int* arr, int low, int high) //快排(递归)
{
if(low < high)
{
int index = partition(arr, low, high);
qsort(arr, low, index-1);
qsort(arr, index+1, high);
}
}
void qsort_no_recursive(int* arr, int low, int high) //快排 (非递归)
{
int pivo = partition(arr, low, high);
stack<int> s;
if(pivo - 1 > low)
{
s.push(low);
s.push(pivo-1);
}
if(pivo + 1 < high)
{
s.push(pivo+1);
s.push(high);
}
while(!s.empty())
{
high = s.top();
s.pop();
low = s.top();
s.pop();
int index = partition(arr, low, high);
if(index - 1 > low)
{
s.push(low);
s.push(index - 1);
}
if(index + 1 < high)
{
s.push(index + 1);
s.push(high);
}
}
}
归并排序
void Merge(int arr[], int low,int mid, int high)
{
int i = low, j = mid+1;
int k = 0;
int* temp = (int*)malloc((high - low + 1) * sizeof(int));
while(i <= mid && j <= high)
{
if(arr[i] < arr[j]) //进行排序存入动态分配的数组中
temp[k++] = arr[i++];
else
temp[k++] = arr[j++];
}
while(i <= mid) //如果前一半还有未处理完的数据,按顺序移入动态分配的数组中
temp[k++] = arr[i++];
while(j <= high) //如果后一半还有未处理完的数据,按顺序移入动态分配的数组中
temp[k++] = arr[j++];
for(i=low, j=0; i<=high; i++)
arr[i] = temp[j++];
free(temp);
}
void Msort(int arr[], int low, int high)
{
if(low < high)
{
int mid = (low + high) >> 1;
Msort(arr, low, mid);
Msort(arr, mid+1, high);
Merge(arr, low, mid, high);
}
}
堆排序
void HeapAdjust(int arr[], int s, int m)
{
int temp = arr[s];
for(int i=2*s; i<=m ; i*=2)
{
if(i < m && arr[i] < arr[i+1])
i++;
if(temp >= arr[i])
break;
arr[s] = arr[i];
s = i;
}
arr[s] = temp;
}
void HeapSort(int arr[], int length)
{
for(int i=length/2; i>=0; i--)
HeapAdjust(arr, i, length-1);
for(int i=length-1; i>0; i--)
{
swap(arr[i], arr[0]);
HeapAdjust(arr, 0, i-1);
}
}
作者:鼠标CS
来源:CSDN
原文:https://blog.csdn.net/hubeidaxuesanqi3012/article/details/65934951
版权声明:本文为博主原创文章,转载请附上博文链接!
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/114903.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...