8种经典排序算法总结
{
while(l <= r)
{
int m = l + (r-1)/2;//为了防止(l+r溢出)
if(arr[m] == x)
return m;
if(arr[m] < x)
l = m + 1;
else
r = m - 1;
}
return -1;
}
{
int m;
while(r - l > l)
{
m = l + (r-l)/2;
if(arr[m] <= x)
l = m;
else
r = m;
}
if(arr[l] == x)
return l;
else
return -1;
}
{
m = l + (r-l)/2;
if(arr[m] <= x)
l = m;
else
r = m;
}
return arr[l];
{
int i,j,min_index;
for(i = 0;i < n;i++)
{
min_index = i;
for(j = i;j < n;j++)
if(arr[j] < arr[min_index])
min_index = j;
swap(&arr[i],&arr[min_index]);
}
}
{
int i,j;
for(i = 0;i < n;i++)
for(j = 0;j < n-i-1;j++)
{
if(arr[j] > arr[j+1])
swap(&arr[j],&arr[j+1]);
}
}
{
int i,key,j;
for(i = 1;i < n;i++)
{
key = arr[i];
j = i - 1;
while(j >= 0 && arr[j] > key)
{
arr[j+1] = arr[j];
j--;
}
arr[j+1] = key;
}
}
{
int n1 = m - l + 1;
int n2 = r - m;
int temp1[n1];
int temp2[n2];
int i,j,k;
for(i = 0;i < n1;i++)
temp1[i] = array[i+l];
for(j = 0;j < n2;j++)
temp2[j] = array[m+1+j];
i = 0;
j = 0;
k = l;
while(i < n1 && j < n2)
{
if(temp1[i] < temp2[j])
{
array[k] = temp1[i];
i++;
k++;
}
else
{
array[k] = temp2[j];
j++;
k++;
}
}
while(i < n1)
{
array[k] = temp1[i];
i++;
k++;
}
while(j < n2)
{
array[k] = temp2[j];
j++;
k++;
}
}
{
if(r - l > 0)
{
int m = l+(r-l)/2;
mergeSort(array,l,m);
mergeSort(array,m+1,r);
merge(array,l,m,r);
}
}
1. Build a max heap from the input data.
2. At this point, the largest item is stored at the root of the heap. Replace it with the last item of the heap followed by reducing the size of heap by 1. Finally, heapify the root of tree.
3. Repeat above steps until size of heap is greater than 1
{
int left = index * 2 + 1;//左子节点的下标
int right = index * 2 + 2;//右子节点的下标
int maxIndex = index;
if(left < maxHeap->size && maxHeap->array[left] > maxHeap->array[index])
maxIndex = left;
if(right < maxHeap->size && maxHeap->array[right] > maxHeap->array[maxIndex])
maxIndex = right;
if(maxIndex != index)
{
swap(&maxHeap->array[maxIndex],&maxHeap->array[index]);
maxHeapify(maxHeap,maxIndex);
}
}
struct MaxHeap * createAndBuildHeap(int * arr,int n)
{
int i;
struct MaxHeap * maxHeap = (struct MaxHeap*)malloc(sizeof(struct MaxHeap));
maxHeap->size = n;
maxHeap->array = arr;
for(i = (maxHeap->size/2)-1;i >= 0;i--)//从下标最大的父节点开始heapify操作
maxHeapify(maxHeap,i);
return maxHeap;
}
void headpSort(int arr[],int n)
{
struct MaxHeap * maxHeap = createAndBuildHeap(arr,n);
while(maxHeap->size > 1)
{
swap(&maxHeap->array[0],&maxHeap->array[maxHeap->size-1]);
maxHeap->size--;
maxHeapify(maxHeap,0);
}
}
{
int i = l - 1;
int target = array[h];
int j;
for(j = l;j <= h-1;j++)
{
if(array[j] <= target)
{
i++;
swap(&array[i],&array[j]);
}
}
swap(&array[i+1],&array[h]);
return i+1;
}
void quickSort(int arr[],int l,int h)
{
if(h > l)
{
int pos = partition(arr,l,h);
quickSort(arr,l,pos-1);
quickSort(arr,pos+1,h);
}
}
{
int gap,i,j,temp;
for(gap = n/2;gap > 0;gap = gap/2)
{
for(i = gap;i < n;i++)
{
temp = arr[i];
for(j = i;j >= gap && arr[j - gap] > temp;j = j - gap)
arr[j] = arr[j - gap];//插入排序
arr[j] = temp;
}
}
}
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。