链表文件
package sort;
public class SqList {
public int LIST_INIT_SIZE = 8;//链表的原始大小
private int INCREMENT = 1;//链表的增量大小
private Object[] SqList = null;//链表
private int curIndex = 0;//当前位置
/**
* 初始化链表
* */
public void initList(){
SqList = new Object[LIST_INIT_SIZE];
}
/**
* 向链表中插入元素
* */
public void insertList(Object o){
if(curIndex > LIST_INIT_SIZE-1){//判断当前链表是否已经满
System.out.println("从新分配空间");
LIST_INIT_SIZE += INCREMENT;
Object []temp = new Object[LIST_INIT_SIZE];
for(int i=0; i<curIndex; i++)
{
temp[i]=SqList[i];
}
SqList = null;
SqList = temp;
}
//链表中如果不让其包含重复元素，则加入这段代码
/*
if(isContain(o))
{
System.out.println("链表中已包含此元素"+o);
}else
{
}
*/
SqList[curIndex++] = o;
}
/**
* 判断链表中是否包含某元素
* */
private Boolean isContain(Object o){
for(int i = 0; i<curIndex; i++){
if(SqList[i].equals(o))
return true;
}
return false;
}
/**
* 删除链表中的某元素
*
* 如果包含重复元素都删除
* */
public void delete(Object o){
for(int i = 0; i<curIndex; i++){
if(SqList[i].equals(o))
{
for(int j=i;j<curIndex-1;j++)
{
SqList[j]=SqList[j+1];
}
curIndex--;
continue;
}
if(i==curIndex-1)
{
System.out.println("不存在此元素"+o);
}
}
}
/**
* 获取链表中的某个元素
* */
public Object getElement(int i)
{
if (i < 0 || i > curIndex)
{
System.out.println("获取位置超出了链表中元素个数"+curIndex);
}
return SqList[i];
}
/**
* 打印链表
* */
public void print()
{
for(int i=0;i<curIndex;i++)
{
System.out.print(SqList[i]+" ");
}
System.out.println();
}
/**
* 交换链表中的两个元素
* */
public void swap(SqList L,int low,int high){
System.out.println("before swap:low-"+SqList[low]+" high-"+SqList[high]);
Object temp = null;
temp = SqList[low];
SqList[low] = SqList[high];
SqList[high] = temp;
System.out.println("after swap:low-"+SqList[low]+" high-"+SqList[high]);
}
}
快排
package sort;
/*快排：两个指针low和high，枢轴记录的关键字为pivotkey，
* 首先从high所指位置起向前搜索，找到第一个关键字小于pivotkey的记录和枢轴记录交换，
* 然后从low所指位置向后搜索，找到第一个关键字大于pivotkey的记录和枢轴记录交换，
* 重复这两步直到low=high为止*/
public class quickSort {
public void QuickSort(SqList L){
QSort(L,0,L.LIST_INIT_SIZE-1);
}
public void QSort(SqList L,int low,int high){
int pivot;
if(low<high){
pivot = Partition(L,low,high);
QSort(L,low,pivot-1);
QSort(L,pivot+1,high);
}
}
public int Partition(SqList L,int low,int high){
System.out.println("start low:"+low+",high:"+high);
int pivotkey;
pivotkey = (Integer) L.getElement(low);//用子表的第一个记录作枢纽记录
System.out.println("pivotkey:"+pivotkey);
while(low<high){//从表的两端交替向中间扫描
while(low<high && (Integer)L.getElement(high)>=pivotkey)
high--;
System.out.println("1-low:"+low+",high:"+high);
L.swap(L,low,high);//将比枢轴记录小的记录交换到低端
while(low<high && (Integer)L.getElement(low)<=pivotkey )
low++;
System.out.println("2-low:"+low+",high:"+high);
L.swap(L,low,high);//将比枢轴记录大的记录交换到高端
}
System.out.println("low:"+low+",high:"+high);
return low;//返回枢轴所在位置
}
public static void main(String[] args) {
SqList sqList = new SqList();
sqList.initList();
sqList.insertList(49);
sqList.insertList(38);
sqList.insertList(65);
sqList.insertList(97);
sqList.insertList(76);
sqList.insertList(13);
sqList.insertList(27);
sqList.insertList(49);
sqList.print();
quickSort quickSort = new quickSort();
quickSort.QuickSort(sqList);
sqList.print();
System.out.println("第2个元素是："+sqList.getElement(1));
System.out.println("第4个元素是："+sqList.getElement(3));
}
}